# Mock exam solution

**(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
*V*_{1 }be the set of vertices of degree 1 in a tree*T*with at least one edge, and*V*_{3 }the set of vertices in*T*of degree at least 3. Show that*|V*_{3}*|*6*|V*_{1}*| −*

**Hint: **Write *V *(*G*) = *V*_{1}*∪V*_{2}*∪V*_{3 }where *V*_{2 }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 *|V*_{3}*| *> *|V*_{1}*| − *2.

**[7 marks] Solution:**

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

2*|E| *= ^{X }*d*(*v*) = *|V |*(2*l *+ 1)*,*

*v∈V*

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

*V*_{1 }*∪ V*_{2 }*∪ V*_{3 }=*V*(*G*), a disjoint union, so (put*n*=_{i }*|V*). We have_{i}|

*n*_{1 }+ *n*_{2 }+ *n*_{3 }= *n.*

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

2*n − *2 = ^{X }*d*(*v*) = ^{X }*d*(*v*) + ^{X }*d*(*v*) + ^{X }*d*(*v*)*.*

*v∈V *(*T*) *v∈V*_{1 }*v∈V*_{2 }*v∈V*_{3}

Hence 2*n − *2 *≥ n*_{1 }+ 2*n*_{2 }+ 3*n*_{3}, i.e.

2*n*_{1 }+ 2*n*_{2 }+ 2*n*_{3 }*− *2 *≥ n*_{1 }+ 2*n*_{2 }+ 3*n*_{3}*.*

Simplifying, *n*_{3 }*≤ n*_{1 }*− *2.

**(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.

- Let ∆(

**[6 marks] Hint: **Use induction on *|V *(*G*)*| *= *n*.

**Solution:**

- Suppose
*χ*(*G*) =*k*. Let*C*_{1}*,…C*be the colour classes. Note all edges go from some_{k }*C*to a different_{i }*C*._{j}

Say that edges between *C _{i }*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 *G ^{0 }*induced by

*V*(

*G*)

*\{v}*has precisely

*n*vertices and not more edges than

*G*, so its maximal degree is at most ∆(

*G*) > ∆(

*G*). By the induction hypothesis,

^{0}*G*can be given a proper colouring with at most ∆(

^{0 }*G*) + 1 6 ∆(

^{0}*G*) + 1 colours. Now consider

*v*, which has at most ∆(

*G*) neighbours in

*G*. We can colour

*v*in compatibility with the subgraph

*G*by choosing a colour among the ∆(

^{0 }⊂ G*G*)+1 colours used on

*G*that has not been used on one of the at most ∆(

^{0 }*G*) neighboursof

*v*. In particular, one may colour

*G*with ∆(

*G*) + 1-colours.

**(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σ*(*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
*I*_{1},*I*_{2}. If there were*A ⊆ I*_{1 }with*|*Γ(*A*)*| < |A|*then let*I*_{3 }be the set*I*_{3 }= (*I*_{2}*\*Γ(*A*))*∪ A*.

*I*_{3 }is independent as there are no edges from *A *to *I*_{2}*\*Γ(*A*). However by assumption *|I*_{3}*| > |I*_{2}*|*, contradicting *|I*_{2}*| *= *α*(*G*).

- If there were an edge in
*V*(*M*)we could add it to^{c }*M*. But*M*is maximum, so*V*(*M*)is edgeless i.e. independent.^{c } - 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*a*_{ij }>

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σ}*

_{(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 ^{P}_{16}*j*_{6}*n a _{ij }*= 1 for all

*i*. In particular, since

*a*= 0 if and only if there is no edge

_{ij }*ij*, we have that for fixed

*i*, 1 = P16

*j*6

*n*

*a*

*ij*= P

*j∈*Γ

*{i}*

*a*

*ij*, so

X X

*a _{ij }*=

*|S| > |*Γ(

*S*)

*|*=

*a*

_{ij}.*i∈S,j∈*Γ(*S*) *i∈*Γ(*S*)*,j∈*Γ(Γ(*S*))

However the sum at the end is at least ^{P}_{i∈S,j∈}_{Γ(S) }*a _{ij}*, so this is a contradiction.

**(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*) =*V*_{1 }*∪ V*_{2}. We show*|V*_{1}*|*=*|V*_{2}*|*and so*|V*(*G*)*|*=*|V*_{1}*|*+*|V*_{2}*|*is even. For contradiction assume (without loss of generality) that*|V*_{1}*| < |V*_{2}*|*, and we start a putative Hamilton cycle with a vertex in*V*_{1}. After 2*|V*_{1}*|*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*|V*_{1}*|*vertices of*V*_{2 }so does not contain all the vertices from*V*_{2 }(since*|V*_{2}*| > |V*_{1}*|*). Hence there is no Hamilton cycle.

- 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*X*=^{c }*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).

- Let
*G*be a graph with 42 vertices that does not contain a*K*_{5 }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.

- Let H denote the complete graph of 12 vertices
*K*_{12 }with one of its cycles of length 3 removed (but not the incident vertices). In other words, H is*K*_{12 }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

- Prove that in a (6
*t*+ 3*,*2*t*+ 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)(*µ − λ*)*−*2*k*

*f,g *= _{}*n − *1 ^{± }_{q}_{ }*.*

- (
*µ − λ*)^{2 }+ 4(*k − µ*)

**[8 marks]**

**Solution: **We have

- (6
*t*+ 2)*t −*4*t −*4

*f,g *= 6*t *+ 2 ^{± }_{q }

*t*^{2 }+ 4(*t*+ 1)- 6
*t*^{2 }*−*2*t −*4^{!}

= = 6*t *+ 2 *± *

*t*+ 2

which are integers so *t *+ 2 divides 6*t*^{2 }*− *2*t − *4 = (*t *+ 2)(6*t − *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).

- 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 *K*_{3 }or an independent set of size *l*. Since *G *does not contain an independent set of size *l *it must have a triangle.

- If
*p*(*n*) =*n*^{−}_{2}, use the first moment method to show^{5 }**whp**that a random graph*G*(*n,p*(*n*)) has no*K*_{3 }(triangle) subgraph .

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

**[16 marks] Solution: **If *p*(*n*) = *n ^{−}*

^{5}_{2 }let

*X*be the number of

*K*

_{3 }in

*G*(

*n,p*(

*n*)). Let

1 if the *i*th 3 vertex subset of *{*1*,…,n} *forms a *K*_{3}

*X _{i }*=

0 if the *i*th 3 vertex subset of *{*1*,…,n} *does not form a *K*_{3}

P(* ^{n}*3)

*X*

*i*so

*E*[

*X*] = P(

*i*=1

*3)*

^{n}*E*[

*X*

*i*].

Then *X *= *i*=1

By independence of the edge probabilities for each potential triangle

*E*[*X _{i}*] =

*P*(

*X*= 1) =

_{i }*p*

^{3 }hence !

*n*

*E*[*X*] = *p*

3

We have that lim* _{n→∞ }E*[

*X*] = 0 so by the First Moment Method we have lim

*(*

_{n→∞ }P*X >*0) = 0 so

**whp**

*G*(

*n,p*(

*n*)) has no triangle.

**END OF MOCK PAPER**