- #1

JaeSun

- 37

- 0

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 infinitely draw out more vertexes ...

but, putting this in word form, i don't know exactly how to do it.

I think that is the proof? that in order to draw out the graph, it can't 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 ?

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 infinitely draw out more vertexes ...

but, putting this in word form, i don't know exactly how to do it.

I think that is the proof? that in order to draw out the graph, it can't 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: