1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph planarity

  1. May 13, 2012 #1
    1. The problem statement, all variables and given/known data
    Prove that for a simple, connected, planar graph, 3f ≤ 2e where f = faces and e = edges

    3. The attempt at a solution
    My professor went over this in class, and mentioned something about "double counting," which I do not really understand. I tried saying that it takes 2 counts to define an edge and 3 to define a face, but from here I am not sure what to do as I am unfamiliar with double-counting proofs.

    Thanks for the help.
     
  2. jcsd
  3. May 13, 2012 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi kinof! :smile:
    every edge has exactly two faces, so slice every edge in two, lengthwise …

    then you have double the number of edges, and every edge has only one face :wink:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Graph planarity
Loading...