# Planar graphs

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 K_{3,3} is not planar.

Also the complete graphs with order 5 and above are not planar.

### Kuratowski theorem

A graph is planar if and only if it doesn't contains an expansion of the complete graph K

_{5}
or bipartite graph K

_{3,3}.

An expansion of a graph is any graph obtained by adding vertices on the edges.

### Euler formula

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 :

### Dual graph

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.