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: Planar graphs with minimum degree

  1. Apr 28, 2005 #1
    ok, here is the question:

    Let G be a graph with minimal degree [tex]\delta[/tex](G) = 5, but suppose there exists only one vertex v[tex]\in V_{G}[/tex] such that d(v) = [tex]\delta[/tex](G). Prove that G is not planar.

    ok, i can do this visually. if i draw the vertex v and its edges to its points, and then draw points, even with the rest of the points having a degree of 6, in order to draw every edge, you will have to keep infintely draw out more vertexes ...

    but, putting this in word form, i dont know exactly how to do it.

    I think that is the proof? that in order to draw out the graph, it cant be planar because you have to keep drawing out vertexes infinitely and will have one crossing.

    the minimum number of vertices is 8 ... trying to draw a complete graph on the other 7 vertices is impossible, and thus, having to draw more vertices, but then you still run into this problem and have to draw more vertices .... the smallest complete/planar graph is [tex]K_{4}[/tex], so it will have a crossing ?
    Last edited: Apr 28, 2005
  2. jcsd
  3. Apr 28, 2005 #2
    Last edited: Apr 28, 2005
  4. Apr 28, 2005 #3
    so maybe I can use the fact that if I can draw a geometric dual graph, then it is planar ... so I Just have to prove that I can't draw one?

    man, i HATE proofs
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook