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 K3,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 K5 or bipartite graph K3,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 :

 S + F = A + 2 

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.

 

Home Arithmetic Geometric Misc Topics Scripts Games Exercices Mail Version Franšaise Previous topic Next topic