MOCK EXAM PGT level 7

Full solutions to all of these mock questions will be provided in the revison lectures in the meantime please attempt these mock questions with open book but under exam time limited conditions.

  1. (a) Let G be a k-regular graph where k > 3 is odd. Prove that G has an even number of vertices.

[3 marks]

(b) Let V1 be the set of vertices of degree 1 in a tree T with at least one edge, and V3 the set of vertices in T of degree at least 3. Show that |V3| 6 |V1| − 2.

[7 marks]

  1. (a) Suppose a graph G has chromatic number χ(G) = k. Show that we can orient the edges of G (i.e. assign each edge precisely one direction) such that every directed path has at most k vertices. [4 marks]

(b) Let ∆(G) denote the largest vertex degree of a simple graph G. Show that G admits a proper colouring with ∆(G) + 1 colours.

[6 marks]

  1. (a) Let G be a graph. Show that there is a perfect matching between two vertex-disjoint independent sets of order the independence number α(G).

[3 marks]

(b) Let M be a maximum matching in a graph G. Show that the complement of V (M) in V (G) is an independent set.

[2 marks]

(c) Let A be an n × n matrix all of whose entries are non-negative and all of whose rows and columns sum to 1. Show that there is a permutation σ of {1,2,…,n} such that a (i) > 0 for all i by using Hall’s theorem.

[5 marks]

  1. (a) Give an example of a graph with vertex connectivity exactly 1 and edge connectivity exactly 2, justifying your claims.

[5 marks]

(b) Let G be a bipartite graph with a Hamilton cycle. Show that G has an even number of vertices.

[5 marks]

  1. Consider the network shown in Figure 5, having source S and sink T. The numbers correspond to the capacity of the network.

Figure 1: A network with source and sink.

  • State the two constraints that must be accounted for when establishing a flow from source to sink in a network.

[4 marks]

  • Prove that the maximum flow is at most 11 using the max-flow min-cut theorem.

Hint: The cut you consider cannot have D and A in the same set.

[6 marks]

  1. Let G be a graph with 42 vertices that does not contain a K5 subgraph and has the maximum possible number of edges. Use Turán’s Theorem to describe (as accurately as the theorem allows) the structure of G. Calculate how many edges G [6 marks]
  2. Let H denote the complete graph of 12 vertices K12 with one of its cycles of length 3 removed (but not the incident vertices). In other words, H is K12 with a triangle of edges removed. Use the Erdös-Stone Theorem to find

ex(n,H) lim .

n→∞ n(n − 1)/2

[7 marks]

  1. Prove that in a (6t + 3,2t + 2,1,t + 1) strongly regular graph, where t ≥ 1 we have that t ∈ {1,2,4,6,10,22}. You may use the fact that the multiplicities of the non-trivial eigenvalues of an (n,k,λ,µ) strongly regular graph are

                

  • (n − 1)(µ − λ) 2k

f,g = n − 1 ± q                                     .

  • (µ − λ)2 + 4(k − µ)

[7 marks]

  1. Use the Erdös-Szekeres upper bound to show that if the graph G on l(l + 1)/2 vertices has independence number α(G) < l then it has a triangle. [5 marks]
  2. (a) If p(n) = n12 , use the first moment method to show whp that a random graph G(n,p(n)) has no triangle subgraph .

(b) If p(n) =  , use the second moment method to show whp that a random

n2

graph G(n,p(n)) has a triangle subgraph .

You must quote any part of the notes which you use in your argument.

[25 marks]

END OF PAPER