Question 1 (10 marks)

Let G be the graph shown below.

v

u

w

x 

z

Answer the following questions.  (You are not required to justify your answer.)

(a) Write down the adjacency matrix of G.   Index rows and columns of this matrix by

vertices of G in alphabetical order.

(b)  Does G contain any bridge? If it does, find all bridges of G.

(c)  Give the exact value of the connectivity of G.

(d)  Give the exact value of the edge connectivity of G.

(e)  Does G contain any perfect matching? If it does, find all perfect matchings in G.

Question 2 (10 marks)

Let G be the graph shown below.

v

u

w

p

x

z

Answer the following questions.  (You are not required to justify your answer.)            (a) Write down the edge set of the subgraph of G induced by }u, v, p, x, z( c V (G).

(b) Is G Hamiltonian? If it is, give a Hamilton cycle of G.

(c) Is G an Eulerian graph?

(d)  Give the exact value of the independence number of G.

(e)  Give the exact value of the chromatic number of G.

Question 3 (20 marks)

Consider the following weighted graph G, where the number next to each edge is its weight.

y

1.5

0.5

w

v

z

Find the (weighted) distance in G from vertex u to every other vertex of G by using Dijkstra’s algorithm. During the course of the algorithm, show how the labels and parents of each vertex change in a table.  Draw a labelled spanning tree of G that contains shortest paths from u to every other vertex.

Question 4 (18 marks)

Let G be a connected graph which is not a tree. Let c(G) be the length of a longest cycle in G. (a)  Prove that G has at least c(G) pairwise distinct spanning trees.

(b)  Give a necessary and sufficient condition for G to have exactly c(G) pairwise distinct

spanning trees. You are not required to prove your statement.

Question 5 (20 marks)

Let N be the network below, where 北 and y are the source and sink, respectively, and the arc capacities are shown next to each arc.  An initial flow of this network is given in parentheses. Starting from this flow, find a maximum flow in N using the labelling algorithm.  Meanwhile, give the minimum cut in N that comes out of the algorithm. Show every stage of the algorithm and label all vertices that can be labelled in each iteration of the algorithm.  State explicitly the value of the maximum flow and the capacity of the minimum cut.

p

q

x

5(0)

u

y

3(2)

w             2.5(2)                v

Question 6 (20 marks)

Let G be the following graph.

a

b                   w                     d

u                  c                     v

(a)  Show that G is bipartite by giving a bipartition of G explicitly.

(b) Using K¨onig-Hall Theorem and the bipartition obtained in  (a), prove that G has no

perfect matchings.

(c)  Construct a maximal alternating tree with root u with respect to the matching M = }aq‘ cw(, and use this maximal alternating tree to find a matching in G with one more edge than M .

Question 7 (12 marks)

Let Kr  be the complete graph with order r and let Ks  be the empty graph with order s (that is, Ks  is the complement of Ks), where r and s are positive integers. Let

G = Kr + Ks

be the join of Kr  and Ks .  Prove that, if s > r 2 1, then G is not tough.  Does G contain any Hamilton cycle when s > r 2 1?

Question 8 (18 marks)

Prove that the order of any 2-connected 3-regular planar graph with no 3-cycles or 4-cycles is at least 20.

Question 9 (18 marks)

Recall that K3,3 is the complete bipartite graph with three vertices in each part of its bipartition. Using Jordan Curve Theorem, but not Euler’s formula or any result derived from it, prove that K3,3  is nonplanar. You are not allowed to use the fact that m < 2n - 4 for any simple bipartite planar graph with order n 2 3 and size m as this result is derived from Euler’s formula.

Question 10 (14 marks)

Let G be the following graph.

p

x          y                     z

 q

Give a linear order v1 , v2 , . . . , v8 of the eight vertices of G such that vi  e V (Gi) is a vertex with minimum degree in Gi  for 1 < i < 8, where G1 = G and Gi  is defined as G - }v1 , . . . , vi − 1 ( for 2 < i < 8.  Using this linear order and Algorithm CoLouRGRAPH, give a proper colouring of G.