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.

  • $\begingroup$ greedIsGoodAha.. Thanks for including the link to the definition. $\endgroup$ – coffeemath Feb 10 '17 at 22:58
  • 1
    $\begingroup$ Simply searching in Google for "maximal planar" "adjacent vertices" returns a few books containing this theorem with a proof. (Although I did not check the proof, but perhaps if you have a look there, it might help you.) $\endgroup$ – Martin Sleziak Feb 11 '17 at 11:25
  • $\begingroup$ It seems that the Wikipedia page you linked (discharge method) uses as an example exactly the theorem you are trying too prove. $\endgroup$ – dtldarek Feb 11 '17 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.