LearnMathOnline

Can we join three houses with three utilities so that none of the connections crosses? Note that the corresponding graph is \(K_{3,3}\). So can we draw \(K_{3,3}\) without edge-crossing?

Definition (Planar graph). A graph is planar if it can be drawn in the plane such that its edges intersect only at their endpoints (i.e., edges do not cross each other). A graph with such a drawing is called a planar embedding of the planar graph.

Example. \(K_4\) is a planar graph. \(K_5\) and \(K_{3,3}\) are not planar.

Definition (Face). A planar embedding of a planar graph splits the plane into regions called faces including an unbounded region called the outer face.

Example. The following planar embedding of \(K_4\) has 4 faces where face \(f_4\) is the outer face.

Theorem (Euler's formula). Let \(G\) be a simple connected planar graph on \(v\) vertices and \(e\) edges. If \(f\) is the number of faces in a planar embedding of \(G\), then \[v-e+f=2.\]

By induction on \(e\), the number of edges of \(G\).

Example. For \(K_4\), we have \(v=4\) and \(e=\binom{4}{2}=6\). By Euler's formula, the number of faces in a planar embedding of \(K_4\) is \[f=e-v+2=6-4+2=4.\]
Problem. Find the number of faces in a planar embedding of a \(3\)-regular connected planar graph \(G\) on 8 vertices.

Solution. Here \(v=8\) and the degree-sum is \(3\cdot 8=24\). So \[e=\frac{1}{2}(\text{the degree-sum})=\frac{1}{2}\cdot 24=12.\] By Euler's formula, the number of faces in a planar embedding of \(G\) is \[f=e-v+2=12-8+2=6.\]
Theorem. Let \(G\) be a simple connected planar graph on \(v\geq 3\) vertices and \(e\) edges. Then the following hold.

Let \(f\) be the number of faces in a planar embedding of \(G\).

(a) The degree of a face \(f_i\), denoted by \(\operatorname{d}(f_i)\), is defined to be the number of edges on the boundary of \(f_i\). Since \(v\geq 3\), the degree of the outer face is at least 3. Since \(G\) has no loops or multiedges, \(\operatorname{d}(f_i)\geq 3\) for each face \(f_i\). Note that each edge is counted twice in the degree-sum of faces. Thus \[2e=\sum_{\text{face } f_i}\operatorname{d}(f_i).\] Since \(\operatorname{d}(f_i)\geq 3\) for each face \(f_i\), we have \[2e=\sum_{\text{face } f_i}\operatorname{d}(f_i)\geq 3f.\] Thus \(f\leq \frac{2}{3}e\). By Euler's formula, \(e-v+2=f\leq \frac{2}{3}e\). Thus \(\frac{1}{3}e\leq v-2\) which implies \(e\leq 3v-6\).

(b) Similar proof.

Problem. Use an upper bound of the number of edges of a planar graph to prove that \(K_5\) and \(K_{3,3}\) are not planar graphs.

Solution. For \(K_5\), \(v=5\) and \(e=\binom{5}{2}=10\). Suppose that \(K_5\) is planar. Then by the above theorem, \(10=e\leq 3v-6=3\cdot5-6=9\), a contradiction. Thus \(K_5\) is not a planar graph.

For \(K_{3,3}\), \(v=6\) and \(e=3\cdot3=9\). Since \(K_{3,3}\) is a bipartite graph, it has no odd cycles. Suppose that \(K_{3,3}\) is planar. Then by the above theorem, \(9=e\leq 2v-4=2\cdot6-4=8\), a contradiction. Thus \(K_{3,3}\) is not a planar graph.

Problem. Prove that if \(G\) is a simple connected planar graph, then \(G\) has a vertex of degree at most 5.

Solution. Let \(v\) and \(e\) be the number of vertices and edges of a simple connected planar graph \(G\) respectively. If \(v=1 \text{ or } 2\), then the result is true. Suppose \(v\geq 3\). Then by (a) of the preceding theorem, \(e\leq 3v-6\). Suppose \(\operatorname{d}(x)\geq 6\) for all vertices \(x\) of \(G\). Then \[e=\frac{1}{2}\sum_{\text{vertex }x}\operatorname{d}(x)\geq \frac{1}{2}(6v)=3v\] which contradicts the fact that \(e\leq 3v-6 < 3v\).

Definition (Subdivision). A subdivision of an edge \(\{u,v\}\) is the path \(uvw\) obtained by inserting a new vertex \(w\) on the edge \(\{u,v\}\). A subdivision of a graph \(G\) is obtained from \(G\) by subdivision of edges in \(G\).

Remark. A graph \(G\) is planar if and only if every subdivision of \(G\) is planar.

Theorem (Kuratowski, 1930). A graph is planar if and only if it does not contain a subdivision of \(K_5\) or \(K_{3,3}\).

(\(\Longrightarrow\)) Since \(K_5\) or \(K_{3,3}\) are nonplanar, their subdivisions are also nonplanar. Thus if a graph is planar, then it does not contain a subgraph that is a subdivision of \(K_5\) or \(K_{3,3}\).
(\(\Longleftarrow\)) Nontrivial proof.

Remark. Applications of planar graphs include designing road networks without underpasses or overpasses and designing electronic circuits on a board without insulated wires. There are interesting topics related to planar graphs such as thickness, crossing number, graph embedding on surfaces (see topological graph theory).

Planar Graphs