Planar graphs

For a connected plane graph $G$,

Apply induction on the number of faces $|F|$. The base case is $|F|=1$. In this case, the plane graph has exactly one external face and every edge is a bridge. Thus, graph $G$ is a tree and necessarily has $|E|=|V|-1$, which satisfies Euler's formula. Assume Euler's formula holds for plane graphs with $|F| = k$ faces. For the plane graph with $|F|=k + 1$, namely $G$, there must be a non-bridge edge $e$ that is incident to two different faces. Delete edge $e$ to obtain $G-e$, which has $|V|$ vertices, $|E|-1$ edges, and $|F|-1$ faces. By the induction hypothesis, Euler's formula holds for $G-e$, namely $|V|-(|E|-1)+(|F|-1)=2$. Rearranging gives Euler's formula for $G$. Therefore, by induction, Euler's formula holds for all plane graphs.

For a plane graph with $k$ connected components, namely $G$, we have

Every connected component of $G$ is a plane graph, but these components share the same external face. Therefore, applying Euler's formula to the components and adding the results gives the correct total numbers of vertices and edges, but overcounts the total number of faces by $(k-1)$, because the single external face is counted $k$ times. Accounting for this correction gives $|V|-|E|+|F| = 2k - (k-1) = k+1$.

For a plane graph with $k$ connected components, namely $G$, if every face of graph $G$ has degree at least $l \ge 3$, then

Since every face of $G$ has degree at least $l$, the sum of all face degrees is at least $l|F|$, namely $2|E| \ge l|F|$. Substituting the corollary $|V| - |E| + |F| = k + 1$ of Euler's formula gives

Using $l \ge 2$, solve for $|E|$ to obtain

Let $G$ be a simple planar graph with $|V|\ge 3$. Then

When $G$ is connected, every face has degree at least $3$. Taking $k=1$ and $l=3$ in the theorem above gives $|E|\le 3|V|-6$.

When $G$ is disconnected, there are two cases:

• If some connected component has at least $3$ vertices, then for each connected component with at least $3$ vertices, establish $|E_i|\le 3|V_i|-6$ separately. Every component with fewer than $3$ vertices necessarily has $|E_i|\le |V_i| \le 3|V_i|$. Adding the inequalities for all connected components gives $|E|\le 3|V|-6$.
• If every connected component has fewer than $3$ vertices, then the whole graph necessarily has $|E|\le |V|$. Since $|V|\ge 3$ implies $|V|\le 3|V|-6$, we still have $|E|\le 3|V|-6$.

This proves the proposition.

Let $G^*$ be the dual graph of a plane graph $G$. Then $G^*$ is a connected plane graph. Moreover, $G^{**}$ is isomorphic to $G$ if and only if $G$ is connected.

The fact that $G^*$ is a plane graph follows from its construction. We also need to prove that graph $G^*$ is connected. For any two vertices in graph $G^*$, namely $v^*_i,v^*_j$, let the line segment connecting $v^*_i$ and $v^*_j$ in the plane pass through the faces and edges of graph $G$ in the sequence $f_i,e_{s_1},f_{s_1},\cdots,f_{s_{r-1}},e_{s_r},f_j$; these correspond to the vertices and edges $v_i^*,e_{s_1}^*,v^*_{s_1},\cdots,v^*_{s_{r-1}},e^*_{s_r},v^*_j$ in the dual graph. By the construction of $G^*$, consecutive vertices and edges in the sequence are incident, so this describes a walk in $G^*$. Hence, graph $G^*$ is connected.

The graph $G^{**}$ is the dual graph of graph $G^*$ and is necessarily connected. Therefore, $G$ is isomorphic to $G^{**}$, and a necessary condition is that graph $G$ be connected. Next, prove that this condition is sufficient. It is enough to show that when graph $G$ is connected, graph $G$ satisfies the construction requirements for the dual graph of graph $G^*$. Because the edges of graph $G^*$ correspond naturally to those of graph $G$, it suffices to show that every face of graph $G^*$ contains exactly one vertex of graph $G$. For any face of graph $G^*$, namely $f^*$, let a boundary edge be $e^*$. Then the corresponding edge in graph $G$, namely $e$, has one endpoint inside face $f^*$; hence face $f^*$ contains at least one vertex of graph $G$. Since graph $G^*$ and graph $G$ are connected, Euler's formula holds; graph $G$ and graph $G^*$ have equal numbers of edges, the number of faces of graph $G$ equals the number of vertices of graph $G^*$, so the number of vertices of graph $G$ equals the number of faces of graph $G^*$. Thus every face of graph $G^*$ contains exactly one vertex of graph $G$. The proposition follows.

For a planar graph $G=(V,E)$ and two vertices $s,t$, there exists a planar embedding of $G$ in which $s,t$ lie on the same face if and only if $(V,E \cup \{(s,t)\}$ is a planar graph.

If there is a planar embedding of $G$ in which $s,t$ lie on the same face, an edge $(s,t)$ can be added inside that face while preserving planarity.

If $(V, E \cup \{(s,t)\})$ is planar, take any planar embedding of it. Then $s,t$ lie on the same face containing the edge $(s,t)$. After deleting $(s,t)$, $s,t$ still lie on the same face. The proposition follows.

Plane graphs (without self-loops) are $4$-colorable.

Every simple planar graph has a planar embedding in which all edges are line segments.

A planar graph has at most $8|V|-16$ maximal cliques.

Every $4$-vertex-connected planar graph is Hamiltonian.

$K_5$ and $K_{3,3}$ are not planar.

As stated earlier, every simple connected plane graph with $|V|\ge 3$ must satisfy

Here, $l$ is the minimum face degree. For $K_5$, $l=3,~|V|=5,~|E|=10$, so $K_5$ cannot be drawn as a plane graph. For $K_{3,3}$, $l=4,~|V|=6,~|E|=9$, so $K_{3,3}$ cannot be drawn as a plane graph.

A graph $G$ is planar if and only if $G$ contains no subgraph homeomorphic to $K_5$ or $K_{3,3}$.

A graph $G$ is planar if and only if $G$ has no subgraph that can be contracted to $K_5$ or $K_{3,3}$.

A maximal planar graph $G$ is necessarily connected. Moreover, when $|V|\ge 3$, $G$ has no bridges.

If a planar graph $G$ is disconnected, then in any planar embedding of $G$ we can choose two vertices belonging to different connected components and connect them inside the external face. The resulting graph is clearly still a plane graph, so graph $G$ is not maximal planar. Therefore, if graph $G$ is maximal planar, it must be connected.

If a planar graph with vertex count $|V|\ge 3$, namely $G$, has a bridge $e=(u,v)$, then after deleting $e$, graph $G - e$ has exactly two connected components, and $u,v$ belong to different components. Suppose the component containing $v$ has at least two vertices. Draw the component containing $u$, namely $G_1$, in the plane, choose any face of graph $G_1$ whose boundary contains $u$, denoted $f$, and draw the other component $G_2$ inside face $f$. Since $G_2$ is simple, the boundary of its external face cannot be a self-loop, so there is at least one other vertex $w\neq u,v$. Connecting $v,w$ to $u$ produces a plane graph containing graph $G$ as a subgraph. Thus, graph $G$ is not maximal planar. Therefore, a maximal planar graph with vertex count $|V|\ge 3$ has no bridges.

For a plane graph with vertex count $|V|\ge 3$, namely $G$, it is a maximal planar graph if and only if it is simple and every face has degree $3$.

The sufficiency is obvious. We only need to establish necessity, namely that every face in a maximal planar graph with vertex count $|V|\ge 3$, namely $G$, has degree $3$. Since $G$ is a connected simple plane graph and $|V|\ge 3$, every face has degree at least $3$. If the proposition were false, there would be a face $f$ whose boundary has length at least $4$. Since $G$ has no bridges, this boundary must be a cycle. Let it be $v_1v_2v_3v_4\cdots v_1$. If $v_1$ and $v_3$ were not adjacent, then, inside face $f$, connecting $v_1$ and $v_3$ would preserve planarity, contradicting the maximality of $G$; hence $v_1$ and $v_3$ are adjacent. Similarly, $v_2$ and $v_4$ are adjacent. However, neither edge $(v_1,v_3)$ nor $(v_2,v_4)$ appears in face $f$. Thus both edges must lie outside face $f$. This is impossible, since no matter how they are drawn, the two edges must intersect. Therefore, $G$ has no face of degree greater than $3$. The proposition follows.

For a graph with vertex count $|V|\ge 3$, namely $G$, the number of edges is always $|E|=3|V|-6$ and the number of faces is $|F|=2|V|-4$.

A graph $G$ is outerplanar if and only if $G$ contains no subgraph homeomorphic to $K_4$ or $K_{2,3}$.

For a maximal outerplane graph with vertex count $|V|\ge 3$, namely $G$, and suppose every vertex lies on the boundary of the external face. Then $G$ has exactly $|V|-2$ internal faces.

Apply induction on $|V|$. The base case is $|V|=3$. Then $G$ is a triangle and has only $1$ internal face, so the proposition holds. Assume it holds for $|V| = k$. We now prove it for $|V| = k+1$.

First, $G$ must have a degree-$2$ vertex. Otherwise, every vertex except neighboring vertices on the external-face boundary would have to be connected to the third vertex. Number the vertices on the external-face boundary consecutively, and for every $i = 1,2,\cdots,k+1$, define $f(i)$ as the smallest index of a vertex connected to vertex $i$ and not adjacent to it in the numbering. Consider the possible values of $f(i)$. First, $1 < f(1)$. Since vertex $1$ is already connected to $f(1)$, the segment from vertex $2$ to $f(2)$ cannot cross edge $(1,f(1))$, so necessarily $1 < 2 < f(2) < f(1)$. Similarly, $2 < 3 < f(3) < f(2)$. Since there are only finitely many vertices, this successively shrinking process must terminate after finitely many steps. Let $i^*$ be the largest value satisfying $1 < \cdots < i-1 < i < f(i) < f(i-1) < \cdots < f(1)$ for $i$. Since vertices $i^*$ and $f(i^*)$ are not adjacent, we necessarily have $i^* < i^* + 1 < f(i^*)$. Repeating the previous argument would still give $i^* < i^*+1 < f(i^*+1) < f(i^*)$, contradicting the maximality of $i^*$. This contradiction shows that $G$ must have a degree-$2$ vertex.

Let $v$ be a vertex of degree $2$. Delete this vertex from graph $G$ to obtain an outerplane graph with $k$ vertices, $G-v$. This graph must be maximal outerplane; otherwise, a legal way to add an edge to it would also be legal for graph $G$. By the induction hypothesis, graph $G-v$ has exactly $k-2$ internal faces, and deleting vertex $v$ reduces one internal face of graph $G$. Therefore, graph $G$ has $k-1$ internal faces. The proposition follows.

For an outerplane graph with vertex count $|V|\ge 3$, namely $G$, and suppose every vertex lies on the boundary of the external face. Then $G$ is maximal outerplane if and only if the boundary of the external face of $G$ is a cycle of length $|V|$ and every internal-face boundary is a cycle of length $3$.

The sufficiency is obvious. Indeed, consider connecting two non-adjacent vertices on the external-face boundary. If the connection is drawn inside the external face, not all vertices can remain on the boundary of one face; otherwise, the segment must intersect the boundary of an internal face.

Now prove necessity. Suppose the boundary of the external face of $G$, $v_1v_2v_3\cdots v_nv_1~(n = |V|)$, is not a cycle. Then it passes through some vertex more than once; that is, there exist $i\neq j$ with $i-j\neq\pm 1\pmod{n}$ such that $v_i=v_j$. Without loss of generality, let $1 < i < j < n$. The edges incident to $v_{i-1}$ can only lie inside the bounded region enclosed by the cycle $v_jv_{j+1}\cdots v_nv_1\cdots v_{i-1}v_i$, while the edges incident to $v_{i+1}$ can only lie inside the bounded region enclosed by the cycle $v_iv_{i+1}\cdots v_{j-1}v_{j}$. Therefore, $v_{i-1}$ and $v_{i+1}$ cannot be adjacent. We can add an edge connecting $v_{i-1}$ and $v_{i+1}$, denoted $e$, to obtain $G+e$. This is clearly also a plane graph, and its external-face boundary contains all vertices. This contradicts the maximal outerplanarity of $G$. Thus, the external face of $G$ must be a cycle of length $|V|$. The reason that every internal-face boundary of $G$ is a cycle of length $3$ is the same as for maximal planar graphs and is omitted.

For a maximal outerplanar graph with vertex count $|V|\ge 3$, namely $G$, there are:

1. $|E|=2|V|-3$.
2. $G$ has at least $3$ vertices of degree at most $3$, and at least $2$ vertices of degree $2$.
3. The vertex connectivity of $G$ is $2$.