A graph is said 'planar'when it can be drawn on a plane
without crossing edges.
Problem : Let three factories producing water, gas and electricity and three towns.
Link each town to each factory without crossing lines.
It is impossible, the bipartite graph K3,3 is not planar.
Also the complete graphs with order 5 and above are not planar.
A graph is planar if and only if it doesn't contains an expansion of the complete graph K5
or bipartite graph K3,3
An expansion of a graph is any graph obtained by adding vertices on the edges.
The edges in a planar graph define regions
, including the infinite region outside the graph.
If a planar connected graph has S vertices F region and A edges, we have :
Given a connected planar graph without single vertices, we deduce a "dual" planar graph G*
Each region of G corresponds to a vertex of G*
Two vertices in G*
are connected by an edge if and only if
the corresponding region in G share a common edge (border).
Four color theorem
This theorem, proved in 1976, says that to colour the region of any planar graph
(lands in a geography chart), four colours suffice.
This is the same as colouring the vertices of the dual graph, hence the equivallent theorem :
Every planar graph is 4-colourable.