Mock exam solution

  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]

  • 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| −

Hint: Write V (G) = V1∪V2∪V3 where V2 is the set of vertices of degree 2 and think about the sums of degrees. Facts about trees and the Handshake Lemma may be used if stated accurately.

Warning: In the original mock exam it was wrongly claimed that |V3| > |V1| − 2.

[7 marks] Solution:

  • We let G = (V,E) and note that d(v) = 2l + 1 > 3 (so l > 1) for all v ∈ V . Then, the Handshake lemma tells us that

2|E| = X d(v) = |V |(2l + 1),

v∈V

so 2 divides |V |(2l + 1) but 2l + 1 is odd so 2 divides |V | and we conclude that G has an even number of vertices.

  • V1 ∪ V2 ∪ V3 = V (G), a disjoint union, so (put ni = |Vi|). We have

n1 + n2 + n3 = n.

We use that trees are connected so there are no isolated vertices. By the Handshake Lemma 2m = PvinV (T) d(v). The number of edges in a tree on n vertices is n − 1, so

2n − 2 = X d(v) = X d(v) + X d(v) + X d(v).

v∈V (T)                                                                                                  v∈V1                                                                                                                                                                   v∈V2                 v∈V3

Hence 2n − 2 ≥ n1 + 2n2 + 3n3, i.e.

2n1 + 2n2 + 2n3 2 ≥ n1 + 2n2 + 3n3.

Simplifying, n3 ≤ n1 2.

  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 [4 marks]
    • 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] Hint: Use induction on |V (G)| = n.

Solution:

  • Suppose χ(G) = k. Let C1,…Ck be the colour classes. Note all edges go from some Ci to a different Cj.

Say that edges between Ci and C − j are directed from i to j if and only if i < j.

Then any path contains at most one element from any colour class, so has at most k vertices.

  • If |V (G)| = n = 1 then ∆(G) = 0 and one colour is enough to colour one vertex.

Assume the result is true for graphs with n vertices and assume that G has |V (G)| = n + 1.

Remove one vertex v from G. Then the graph G0 induced by V (G)\{v} has precisely n vertices and not more edges than G, so its maximal degree is at most ∆(G) > ∆(G0). By the induction hypothesis, G0 can be given a proper colouring with at most ∆(G0) + 1 6 ∆(G) + 1 colours. Now consider v, which has at most ∆(G) neighbours in G. We can colour v in compatibility with the subgraph G0 ⊂ G by choosing a colour among the ∆(G)+1 colours used on G0 that has not been used on one of the at most ∆(G) neighboursof v. In particular, one may colour G with ∆(G) + 1-colours.

  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]

  • 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]

  • 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.

Hint: Make an appropriate bipartite graph whose vertex classes are the rows and columns.

[5 marks]

Solution:

  • Make a bipartite graph whose vertex classes are the two maximum independent sets I1, I2. If there were A ⊆ I1 with |Γ(A)| < |A| then let I3 be the set I3 = (I2\Γ(A)) ∪ A.

I3 is independent as there are no edges from A to I2\Γ(A). However by assumption |I3| > |I2|, contradicting |I2| = α(G).

  • If there were an edge in V (M)c we could add it to M. But M is maximum, so V (M)c is edgeless i.e. independent.
  • We make a bipartite graph by having one vertex class the rows of A, the other the columns, with an edge between row i and column j if and only if aij >

We claim that for any set S of rows there are at least as many columns adjacent to at least one element of S, this will suffice by Hall’s theorem. Indeed, in that case the perfect matching will cover each of the columns and it will map them to each of the rows. In turn this means that for each i we have a σ(i) (the one given by the only edge coming out of the column i) such that a(i) > 0.

So suppose we do not have a perfect matching. Then, by Hall’s Theorem, we would have (writing Γ(S) for {v ∈ V : v ∼ s for some s ∈ S} as usual) that there is some S for which |S| > |Γ(S)|.

By definition of the matrix we have that P16j6n aij = 1 for all i. In particular, since aij = 0 if and only if there is no edge ij, we have that for fixed i, 1 = P16j6n aij = Pj∈Γ{i} aij, so

X                            X

aij = |S| > |Γ(S)| =                                                         aij.

i∈S,j∈Γ(S)       i∈Γ(S),j∈Γ(Γ(S))

However the sum at the end is at least Pi∈S,j∈Γ(S) aij, so this is a contradiction.

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

[5 marks]

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

[5 marks] Solution:

  • Let G be the graph consisting of two triangles sharing a vertex labelled as 1, with {2,3} the other vertices of the left triangle and {4,5} the other vertices of the right triangle.

This has κ = 1 as G is connected but removing 1 disconnects G.

However λ(G) > 2 because any one edge can be removed without disconnecting G.

However, e.g. removing two edges incident with any of {2,3,4,5} disconnects G. Thus δ(G) = 2.

  • Let the vertex partition be V (G) = V1 ∪ V2. We show |V1| = |V2| and so |V (G)| = |V1| + |V2| is even. For contradiction assume (without loss of generality) that |V1| < |V2|, and we start a putative Hamilton cycle with a vertex in V1. After 2|V1| edges have been traversed we are back at the vertex where we started (since we are not allowed to repeat any vertices). But the cycle contains |V1| vertices of V2 so does not contain all the vertices from V2 (since |V2| > |V1|). Hence there is no Hamilton cycle.
  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.

(a) 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 must have B and A in the same set.

[6 marks]

Solution:

  • First, the flow of an edge must not exceed the given capacity. Second, for every vertex except for the source and the sink, the incoming flow is equal to the outgoing flow.
  • Using the hint, we take the cut given by X = {S,A,B} and Xc = V (G)\X. Hence, the capacity of the cut is 4+4+3 = 11, so by the max-flow/min-cut theorem, the capacity of the network is at most 11 (a minimum cut must have capacity at most 11).
  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 [12 marks]

Solution: Turán’s theorem says that the extremal graph is a complete 4-partite graph with the vertex classes of orders as equal as possible. Given that there are 42 vertices, the classes must have orders 11,11,10 and 10.

Each vertex in a class of order 11 is adjacent to every vertex not in that class, so has degree 31. Every vertex in a class of order 10 is adjacent to every vertex outside that class, so has degree 32.

Thus the sum of all degrees is (2 · 11 · 31) + (2 · 10 · 32). then divide by 2 by the Handshake Lemma.

  1. 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.. Find. Use the Erdös-Stone Theorem to find

ex(n,H) lim .

n→∞ n(n − 1)/2

[9 marks]

Solution: H has chromatic number 10 (brief justification needed) : χ(H) = 10.

The Erdös-Stone Theorem implies

ex(n,H)                                                    1                                                    1                       8

lim  = 1  = 1 = . n→∞ n(n − 1)/2 χ(H) 1 10 1 9

  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 − µ)

[8 marks]

Solution: We have

                

  • (6t + 2) t − 4t − 4

f,g = 6t + 2 ± q                                           

  • t2 + 4(t + 1)
  • 6t2 2t − 4!

=    =  6t + 2 ±

  • t + 2

which are integers so t + 2 divides 6t2 2t − 4 = (t + 2)(6t − 14) + 24 so t + 2 divides 24, so is one of 1,2,3,4,6,8,12,24, which implies that t is one of 1,2,4,6,10,22 (since t ≥ 1).

  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]

Solution: By Erdös-Szekeres we have R.

Any graph with l(l + 1)/2 vertices either contains a complete subgraph K3 or an independent set of size l. Since G does not contain an independent set of size l it must have a triangle.

  1. If p(n) = n25 , use the first moment method to show whp that a random graph G(n,p(n)) has no K3 (triangle) subgraph .

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

[16 marks] Solution: If p(n) = n52 let X be the number of K3 in G(n,p(n)). Let

1   if the ith 3 vertex subset of {1,…,n} forms a K3

Xi =

0   if the ith 3 vertex subset of {1,…,n} does not form a K3

P(n3) Xi so E[X] = P(i=1n3) E[Xi].

Then X =        i=1

By independence of the edge probabilities for each potential triangle

E[Xi] = P(Xi = 1) = p3 hence  ! n

E[X] =            p

3

We have that limn→∞ E[X] = 0 so by the First Moment Method we have limn→∞ P(X > 0) = 0 so whp G(n,p(n)) has no triangle.

END OF MOCK PAPER