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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted

Similar Discussions: Graph theory problem
  1. Graph theory (Replies: 5)

  2. Graph theory (Replies: 10)

  3. Graph Theory (Replies: 3)

  4. Graph Theory (Replies: 1)