Prove that every planar graph is 4-vertex-colourable then every plane graph is 4-face-colourable

615 Views Asked by At

This statement is in BondyMurty text book. every planar graph is 4-vertex-colourable then every plane graph is 4-face-colourable the book said it's a direct consequence of the fact that the dual of a plane graph is planar

so we have that number of edges in a Graph and its dual is rhe same = 2q and the degree of every vertex in dual is number of edges of that field using these facts can we prove this statement?

1

There are 1 best solutions below

0
On

I'm not sure what you mean by the number of edges being $2q$, but as Bondy & Murty hint the proof only uses the definition of the dual graph (https://en.wikipedia.org/wiki/Dual_graph).

Take a planar graph $P = (V,E)$, with faces $F$ (for some planar embedding). The dual $D$ of $P = (F,I)$ has vertex set $F$ and an edge $i = (f_1,f_2) \in I$ between two vertices $f_1,f_2$ of $F$ whenever they share an edge in $P$ (as faces). Since $P$ is planar $D$ is planar (as Bondy & Murty state), so it must be $4$-vertex-colourable.

Take any proper $4$-vertex-colouring of $D$, that is a colouring of $F$ (as vertices of $D$) such that no adjacent $f_1,f_2$ in $D$ have the same colour. Then, $f_1,f_2$ being adjacent as vertices of $D$ means by definition that faces $f_1,f_2$ share an edge in $P$ as faces. Combining those, this means that we have coloured $F$ such that no two faces of $F$ sharing an edge (in $P$) are coloured the same, which is a proper $4$-face colouring of $P$.