graph theoryplanar-graphs
o
|
o--o--o
|
o
(the dashed lines represent arcs and o represents nodes)
I can't see any way this graph contains a subgraph homeomorphic to K5 or K3,3 so by Kuratowski's theorem this suggests the graph is planar.
Four Colour theorem says that the vertices of every planar graph can be coloured with at most four colours so that no two adjacent vertices receive the same colour.
So why is the graph above 5-colourable?
Affirmed.
I offer the following (hopefully constructive) criticisms:
"We can see that the original graph has a subgraph homeomorphic to $K_{3,3}$ by redrawing it as follows: [[blah blah blah]]. Therefore it's not planar by Kuratowski's Theorem."
These were drawn using TikZ. Here's the LaTeX code:
\begin{tikzpicture}
\tikzstyle{vertex}=[circle,draw=black,fill=black!20,minimum size=18pt,inner sep=0pt]
\draw (0,0) node (c){};
\draw (c)++(0*360/4+135:3) node[vertex] (A){$A$};
\draw (c)++(1*360/4+135:3) node[vertex] (C){$C$};
\draw (c)++(2*360/4+135:3) node[vertex] (D){$D$};
\draw (c)++(3*360/4+135:3) node[vertex] (B){$B$};
\draw (c)++(0*360/4+135:1.5) node[vertex] (E){$E$};
\draw (c)++(1*360/4+135:1.5) node[vertex] (G){$G$};
\draw (c)++(2*360/4+135:1.5) node[vertex] (H){$H$};
\draw (c)++(3*360/4+135:1.5) node[vertex] (F){$F$};
\draw[ultra thick] (A) -- (B) -- (D) -- (C) -- (A);
\draw[ultra thick] (A) -- (E) -- (H) -- (D);
\draw[ultra thick] (B) -- (F) -- (G) -- (C);
\draw[ultra thick] (E) -- (G);
\draw (F) -- (H);
\end{tikzpicture}
and for the second drawing:
\begin{tikzpicture}
\tikzstyle{vertex}=[circle,draw=black,fill=black!20,minimum size=18pt,inner sep=0pt]
\draw (0,0) node (c){};
\draw (c)++(0,3)++(2,0) node[vertex] (G){$G$};
\draw (c)++(0,3) node[vertex] (A){$A$};
\draw (c)++(0,3)++(-2,0) node[vertex] (D){$D$};
\draw (c)++(-2,0) node[vertex] (E){$E$};
\draw (c) node[vertex] (C){$C$};
\draw (c)++(2,0) node[vertex] (B){$B$};
\draw (c)++(-2,1.5) node[vertex] (H){$H$};
\draw (c)++(2,1.5) node[vertex] (F){$F$};
\draw[ultra thick] (A) -- (B) -- (D) -- (C) -- (A);
\draw[ultra thick] (A) -- (E) -- (H) -- (D);
\draw[ultra thick] (B) -- (F) -- (G) -- (C);
\draw[ultra thick] (E) -- (G);
\draw (F) -- (H);
\end{tikzpicture}
The existence of a $K_5$ would be a local obstruction to four-colourability. There could also be global obstructions, which need to be eliminated too.
The proof shows that all potential obstructions are essentially local, and then systematically shows that they are not obstructions. The configurations which have to be considered are rather larger than $K_5$.
Note that a single region surrounded by a ring of an odd number of others (say seven) requires four colours. But this configuration does not contain four regions which are mutually adjacent ($K_4$). So local obstructions to three-colourability are more complex than we might first think.
Of course, since the four colour theorem is true, the absence of $K_5$ or $K_{3,3}$ does imply that the graph is planar and four colourable. The first of these is easily shown. No-one knows an easy way of proving the second
Best Answer
I'm not by any means an expert in graph theory (in fact, I have little to no knowledge on the subject), but still I'll point out that you can indeed color this graph with only two colours. That's because no arc connects to any of the sorrounding ones except for the middle one, so your "leaf" vertices do not "touch" if you were to draw a map resembling this diagram.
You could also have all the vertices as drawn areas touching each others, making this diagram:
and you could still colour this one with only three colours: two vertices opposing the centre one don't actually connect.
For example, you could have green for the middle one, yellow for the top and the bottom ones, and blue for the left and right ones.
Anyway, keep in mind that the Four Colour Theorem says that you can colour it with at most four colors - if you were to be extremely conservative about the number of colours to use. But in facts, you may as well colour the map with as many colours as the number of vertices in your graph.