Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph theory problem

  1. Nov 9, 2003 #1
    Let G be a maximal planar graph.
    I am having difficulty showing two properties:
    (i) Show that a maximal planar graph is connected.
    For this one I am fairly sure how the proof should go, I just can't seem to arrive at the desired result. If I showed the conclusion fails, then I can add an edge, obtaining a planar graph. Perhaps there is an easier way.
    (ii) Show that a maximal planar graph is no bridges.
    Again, the same way as (i), I just can't seem to get anywhere.

    there were a few other properties that I was able to prove, but for some reason these are giving me some trouble. Any help is greatly appreciated :smile:
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?