Combinatorics

14.1.18.1 Proof. Trees are bipartite (they have no cycles at all, so certainly do not have any cycles of odd length), so Theorem 14.1.17 tells us that they are class one. ◾

14.1.18.2 Proof. The proof is by contradiction: suppose \(\displaystyle n\) is odd, and the cycleis class one. Since every vertex of \(\displaystyle C_n\) has valency two, this means that the graph has a proper edge-colouring that uses only \(\displaystyle 2\) colours. Let us call the colours red and blue.

Assume, without loss of generality, that the edge \(\displaystyle v_0v_1\) is red. The edge \(\displaystyle v_1v_2\) cannot be the same colour as \(\displaystyle v_0v_1\) (because they are both incident to \(\displaystyle v_1\)), so \(\displaystyle v_1v_2\) must be blue. The edge \(\displaystyle v_2v_3\) cannot be the same colour as \(\displaystyle v_1v_2\) (because they are both incident to \(\displaystyle v_2\)), so \(\displaystyle v_2v_3\) must be red. Continuing in this way, we see (by induction on \(\displaystyle k\)) that \(\displaystyle v_kv_{k+1}\) is red whenever \(\displaystyle k\) is even, and it is blue whenever \(\displaystyle k\) is odd. (That is, the two colours must alternate red, blue, red, blue, red, blue,… as we go around the cycle.)

In particular, since \(\displaystyle n\) is odd, we know that \(\displaystyle n-1\) is even, so this means that the edge \(\displaystyle v_{n-1}v_n\) is red. However, we have \(\displaystyle v_n = v_0\) so the edges \(\displaystyle v_{n-1}v_n\) and \(\displaystyle v_0v_1\) are both incident to the vertex \(\displaystyle v_0\)), so they cannot be the same colour. The contradicts the fact that both edges are red. ◾

14.2.5.1 The following \(\displaystyle 2\)-colouring of the edges of \(\displaystyle K_6\) has no solid triangle and no dotted \(\displaystyle K_4\) (because the solid edges form \(\displaystyle K_{3,3}\text{,}\) which has no cycles of odd length, and each connected component of the dotted graph is only \(\displaystyle K_3\)):

14.2.5.3 Proof. We prove this by induction on \(\displaystyle k+\ell\text{.}\)

Base case: \(\displaystyle k + \ell = 2\) (so \(\displaystyle k = \ell = 1\)). Then

So the inequality is valid in the base case.

Inductive step: Assume \(\displaystyle k + \ell \ge 2\text{,}\) and that \(\displaystyle R(k',\ell') \le 2^{k' + \ell'}\text{,}\) whenever \(\displaystyle k' + \ell' \lt k + \ell\text{.}\) Since \(\displaystyle R(k,\ell) = R(\ell, k)\text{,}\) we may assume \(\displaystyle k \le \ell\) (by interchanging \(\displaystyle k\) and \(\displaystyle \ell\text{,}\) if necessary). If \(\displaystyle k = 1\text{,}\) then

Therefore, we may assume \(\displaystyle 2 \le k \le \ell\text{.}\) Since \(\displaystyle (k-1) + \ell \lt k + \ell\) and \(\displaystyle k + (\ell-1) \lt k + \ell\text{,}\) the induction hypothesis tells us that

Therefore, we see from Proposition 14.2.4 that

This completes the proof. ◾

14.2.5.4 Since \(\displaystyle R(k,\ell) \le R(k',\ell')\) whenever \(\displaystyle k \le k'\) and \(\displaystyle \ell \le \ell'\text{,}\) we haveAlso, since \(\displaystyle R(k,\ell) \le R(k-1,\ell) + R(k,\ell-1)\) and \(\displaystyle R(2,\ell) = \ell\text{,}\) we haveSo \(\displaystyle 40 \le R(3,11) \le 53\text{.}\)

14.2.7.2 Proof. We assume that \(\displaystyle N-1 > (c+1)(n-1)\text{.}\) Consider an arbitrary colouring of the edges of \(\displaystyle K_N\) with \(\displaystyle c+1\) colours. Fix a vertex \(\displaystyle v\text{.}\) Since \(\displaystyle v\) has \(\displaystyle N-1>(n-1)(c+1)\) incident edges, the generalised pigeonhole principle tells us that there must be some set of at least \(\displaystyle n\) edges incident with \(\displaystyle v\) that are all coloured with the same colour, say colour \(\displaystyle i\text{.}\) Look at the induced subgraph of \(\displaystyle K_N\) on the \(\displaystyle n\) other endpoints of these edges. If any edge \(\displaystyle xy\) of this induced subgraph is coloured with colour \(\displaystyle i\text{,}\) then all of the edges of the triangle \(\displaystyle \{v,x,y\}\) have been coloured with colour \(\displaystyle i\text{,}\) so \(\displaystyle K_N\) has a monochromatic triangle.

If on the other hand no edge of the induced subgraph has been coloured with colour \(\displaystyle i\text{,}\) then the induced subgraph is a \(\displaystyle K_n\) whose edges have been coloured with the remaining \(\displaystyle c\) colours. By hypothesis, every such colouring has a monochromatic triangle. This completes the proof. ◾

14.2.9.1 We are looking for the smallest value of \(\displaystyle n\) such that every edge-colouring of \(\displaystyle K_n\) with dotted, dashed, and solid lines has either a dashed \(\displaystyle K_2\) or a dotted \(\displaystyle K_2\) or a solid triangle. The following colouring shows that \(\displaystyle R(2,2,3)>2\text{:}\) However, \(\displaystyle R(2,2,3)=3\text{.}\) This is because if any edges are dotted or dashed, then there is a dotted or dashed \(\displaystyle K_2\text{;}\) if no edges are dotted or dashed, then every edge is solid, so there is a solid \(\displaystyle K_3\text{.}\)

14.2.9.2 We will show that \(\displaystyle R(2,4)=4\text{.}\) We are looking for the smallest value of \(\displaystyle n\) such that every edge-colouring of \(\displaystyle K_n\) with dashed or solid lines has either a dashed \(\displaystyle K_2\) or a solid \(\displaystyle K_4\text{.}\) The following colouring shows that \(\displaystyle R(2,4)>3\text{;}\) However, in \(\displaystyle K_4\) if any edge is dashed, then there is a dashed \(\displaystyle K_2\text{,}\) while if no edges are dashed, then there is a solid \(\displaystyle K_4\text{.}\)

14.3.14.2 Proof. We will proceed by induction on \(\displaystyle n\text{.}\)

Base case: \(\displaystyle n=1\text{.}\) Then \(\displaystyle K_1\) is the graph with one vertex and no edges, and \(\displaystyle \chi(K_1)=1\text{.}\) Thus, when \(\displaystyle n=1\) we have \(\displaystyle \chi(K_n)=n\text{.}\)

Induction step: We begin with the induction hypothesis. Let \(\displaystyle k \ge 1\) be arbitrary, and assume that \(\displaystyle \chi(K_k)=k\text{,}\) so we can properly colour \(\displaystyle K_k\) using \(\displaystyle k\) colours, and \(\displaystyle k\) colours are required to do so.

Now consider the graph \(\displaystyle K_{k+1}\text{.}\) Let \(\displaystyle v\) be an arbitrary vertex of this graph. By our induction hypothesis, \(\displaystyle \chi(K_{k+1}\setminus\{v\})=k\text{.}\) Thus, any proper colouring of \(\displaystyle K_{k+1}\) must use at least \(\displaystyle k\) colours on the vertices other than \(\displaystyle v\text{.}\) It is not possible to colour \(\displaystyle v\) with any of these \(\displaystyle k\) colours (since \(\displaystyle v\) is adjacent to all of the other vertices, so has a neighbour that is coloured with each of these \(\displaystyle k\) colours). Therefore, \(\displaystyle \chi(K_{k+1}) \ge k+1\text{.}\) In fact, since \(\displaystyle v\) is the only vertex not yet coloured by these \(\displaystyle k\) colours, it is clear that \(\displaystyle k+1\) colours suffice to colour the graph: we colour \(\displaystyle v\) with a new colour, which is the \(\displaystyle (k+1)\)st colour. This will certainly be a proper colouring of \(\displaystyle K_{k+1}\text{.}\) Thus, \(\displaystyle \chi(K_{k+1}) =k+1\text{,}\) completing the induction step.

By the Principle of Mathematical Induction, \(\displaystyle \chi(K_n)=n\) for every \(\displaystyle n \ge 1\text{.}\) ◾

14.3.14.4 The fact that \(\displaystyle G\) contains a subgraph isomorphic to \(\displaystyle K_i\) implies that \(\displaystyle \chi(G) \ge i\text{.}\) The fact that \(\displaystyle \Delta(G) \le j\) implies thatSo \(\displaystyle 4\le i \le \chi(G)\le j+1 \le 7\text{.}\) If we also know that \(\displaystyle G\) is connected and is neither a complete graph nor a cycle of odd length, then \(\displaystyle \chi(G) \le \Delta(G) \le j\text{,}\) so \(\displaystyle 4 \le i \le \chi(G)\le j \le 6\) in this case.