I'm trying to prove that any maximal planar graph that has more than 3 vertices will have a minimum degree of 3, that is any vertex in such a graph has greater or equal to 3 edges connected to itself. So it doesn't have to have a degree 3 vertex. I want to prove that when there's a degree 2 vertex in a planar graph G (say the rest of G is already maximal), why it is always possible to add at least another edge to the degree 2 vertex to form a maximal planar graph (without crossing).
I can visualize a worst case where a new vertex (u) is added to a maximal planar graph (G) and lands in a triangle formed by three vertices that are previously added to the graph. The only option for u is to connect with the three vertices of the triangle since a fourth edge trying to connect u and the "outside" will cross at least one edge, resulting in a non-planar graph. If u lands outside G, then it should be able to connect to at least three vertices without crossing any edges since G's outer face should also be bounded by three edges, which means that at least three vertices on the verge of G can be connected to u?
How to formally prove the minimum degree of a maximal planar graph G (with more than 3 vertices) is 3?
Best Answer
Given a planar graph, embedded in the plane, you want to add a number of edges to get a maximal planar graph, and you want to be sure that resulting maximal planar graph won't have vertices with degree $=2$.
From this Wikipedia page:
The process of adding edges is straightforward - you need to find all faces, bounded by more than $3$ edges (including the external face), and triangulate these faces by adding new edges.
Let's consider the case, which looks problematic to you - a vertex $u$ with degree $2$, for which it's impossible to add a new edge, incident to the $u$. You have two vertices $v$ and $w$, adjacent to the vertex $u$, and two faces, partially bounded by edges $\{v,u\}$ and $\{u,w\}$. If a new edge, incident to the vertex $u$, can't be added, then both these faces should have an edge $\{v,w\}$, which prevents this addition. So, the graph contains two parallel edges $\{v,w\}$, which is not possible, because we consider simple graphs only.