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

Homework Help: 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:
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook