Chromatic Contradiction Proof

Question

Show that there is no graph of order $6$ and size $13$ that has chromatic number $3$.

Any hints or solutions will be of great help.

Answer 1

A graph of order 6 and size 13 is a $K_6$ missing 2 edges. If it misses 2 adjacent edges $uv$ and $vw$ it contains $K_6-v=K_5$ as a subgraph. If it misses 2 non-adjacent edges $uv$ and $xy$ it contains $K_6-u-x=K_4$ as subgraph.

Answer 2

A $3$-colorable graph of order $6$ has $x$ red vertices, $y$ white vertices, and $z$ blue vertices, where $x+y+z=6$. The number of edges is at most $xy+xz+yz$. Since the maximum of $xy+xz+yz$ subject to the constraint $x+y+z=6$ is $12$, the graph has at most $12$ edges.

Or just quote Turán's theorem: a $K_4$-free graph of order $n$ has at most $\frac{n^2}3$ edges; in particular, a $K_4$-free graph of order $6$ has at most $12$ edges. Hence a graph with $6$ vertices and $13$ edges must contain a $K_4$, so it can't be $3$-colorable.