Example Gas, Water, Electricty Problem. Is there any way to connect each of the three houses to each of the three utilities in such a way that none of the supply lines cross?

Example A pictorial representation of the cube graph that makes it easy to see why it is called the cube graph resembles:

.

This representation includes many "edge crossing." It is possible to re- draw the cube graph so that no two edges cross. Coloring the vertices and edges shows how the graph is re-drawn more clearly.

Definition A plane graph is one that has been drawn in the plane in such a way that its edges intersect only at their common end-vertices.

Definition Two graphs, G and H are defined to be homeomorphic if you can make one graph into the other by inserting vertices of degree 2.

Theorem (Kuratowski's Theorem) A finite graph G is planar if and only if it has no subgraph that is homeomorphic to the complete graph in five vertices (K₅) or the complete bipartite graph K_{3, 3}.

Definition Examples of edge contractions.

Theorem A finite graph G is planar if and only if it contains no subgraph that is edge- contractible to K₅ or K_{3, 3} .

Example The Petersen graph may be represented pictorially as:

Since the Petersen graph is edge contractible to K₅, it is not a planar graph.

Euler's Polyhedron Formula

Definition Let G be a plane graph, and consider the regions bounded by the edges of G. These are called faces.

Example The following graph has 8 faces (one of them is colored yellow - the outside of the graph is usually called the infinite face), 9 vertices and 15 edges.

Theorem If G is a connected plane graph with n vertices, m edges and f faces, then:

Proof (By induction on m.) Suppose that m = 0. Then for G to be a connected graph, there may be only one vertex, and one face. So

and the formula works in the m = 0 case. For the m = 1 case, there are 2 possibilities.

So, Euler's Polyhedron Formula works for m =< 0. For the inductive step, assume that m > 1 is given, and that the Euler Polyhedron Formula works for all graphs with m - 1 edges.
If G is a tree, then f = 1 and m = n- 1. So,

provided that G is a tree. If G is not a tree, then remove an edge e belonging to some circuit. After removing the edge, e, you are left with a plane graph H on n vertices with m - 1 edges. Denote the number of vertices of H by n_H, the number of edges of H by m_H, and the number of faces of H by f_H. Then, n_H = n, m_H = m - 1, and f_H = f - 1. Since m_H = m - 1, H satisfies the Euler Polyhedron Formula, so:

.

Thus, G satisfies the Euler Polyhedron Formula. This completes the proof of the theorem.

Corollary If G is a (connected) simple, finite planar graph with n vertices (n >= 3), then G has at most 3n - 6 edges. Furthermore, if G contains no triangles, then G has at most 2n - 4 edges.

Proof Suppose that G has at most m edges, consider some plane drawing of G, with f faces. Consider the number of pairs (e, F) where e is one of the edges bounding the face F, viz:

For each edge e, there are at most 2 faces that it bounds. So, the total number of these edge face pairs has to be less than 2m. On the other hand, because G is a simple graph, each face is bounded by at least 3 edges. Therefore, the total number of edge-face pairs is greater than or equal to 3f.

So, 3f =< 2m.

By the Euler Polyhedron Formula, n - m + f = 2, , so, 3n - 3m + 3f = 6. Since 3f =< 2m,

.

Re-arranging,

.

Next, if G has no triangles, each face must be be bounded by 4 or more edges. Then 2f =< m, and m =< 2n - 4. This completes the proof of the corollary.

Note This corollary is true even for disconnected, simple, finite planar graphs, provided that each connected component has at least three vertices.

Corollary Every finite, simple, planar graph has a vertex of degree less than 6.

Proof Suppose that G is such a graph. Without loss of generality, G is connected. Suppose that G has n vertices, m edges, and that vertex j has degree d_j (for 1 =< j =< n). Then,

.

Then, the average degree of the vertices of the graph G, is given by,

Average Degree =< .

So, at least one of the vertices has degree less than 6. This completes the proof of the corollary.

Definition Suppose that G is a (finite) connected plane graph, then its dual G^* may be defined as follows:

Take as the vertices of G^* the faces of G, and for every pair of faces having an edge, e, in common, join the corresponding vertices in G^* by an edge that crosses the edge, e, only once.

Example In the following, the graph is indicated in black, and its dual is drawn in red.