# TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 37

Let G be an undirected simple graph and ${\displaystyle H}$ a subgraph of ${\displaystyle G}$ satisfying ${\displaystyle H\cong K_{n}}$ for some ${\displaystyle n}$. What can be said about the relation between ${\displaystyle \chi (G)}$ and ${\displaystyle \chi (H)}$? Find a graph ${\displaystyle G}$ with ${\displaystyle \chi (G)=3}$ which does not have a ${\displaystyle K_{3}}$ as a subgraph.

## Solution

Since ${\displaystyle G}$ contains a sub-graph ${\displaystyle H}$ isomorph to ${\displaystyle K_{n}}$ the minimum number of colours needed to colour the whole graph is at least the number needed to colour ${\displaystyle H}$. This means to colour ${\displaystyle G}$ we need at least ${\displaystyle n}$ colours:

   ${\displaystyle \chi (G)\geq \chi (H)=n}$


The figure below shows a three-colourable graph, which does not contain ${\displaystyle K_{3}}$.