ok, here is the question:(adsbygoogle = window.adsbygoogle || []).push({});

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 ?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Planar graphs with minimum degree

**Physics Forums | Science Articles, Homework Help, Discussion**