Edit: A maximimal planar graph is a planar graph in which every face, including the unbounded face, is bordered by exactly three edges. Wikipedia.
Prove that a maximal planar (sometimes called triangulated planar) graph has one one of the following properties
- A node of degree 1, 2, 3, or 4.
- Two adjacent nodes of degree five.
- A node of degree five adjacent to a node of degree six.
To satisfy the first condition, I observe that from the most basic maximal planar graph is a graph of three nodes where each node is of degree 2 (the triangle graph). In order to maintain triangularity within the graph, if a new node is added, then three new edges must also be added to the graph. This means that when there are four nodes, an edge is drawn to every existing node, so every node is of degree 3. Therefore, when there is a fifth node added, there must exist two nodes of degree 4.
Then if another node is added, $n_k$, and an edge connects $n_k$ and a node which previously had degree 4, in order to protect the triangularity of the unbounded face, an edge must also connect $n_k$ to a different node which formerly had degree 4. This satisfies the second condition.
I use the discharge method to prove the second and third conditions in a more general sense, but I don't really see what the relationship between a positive charge and planar triangularity is. I also suspect that my proof for the first condition suffers from build-up error, but I don't know how I can approach the problem from in a more general sense.