Planar graphs with minimum degree

In summary, the conversation discusses how to prove that a graph with minimal degree 5 and only one vertex with a degree of 5 is not planar. The proof involves drawing out the graph visually and showing that it is impossible to do so without having a crossing. The minimum number of vertices for this graph is 8, and even with more vertices, the problem persists. The concept of dual graphs is also mentioned, as well as the fact that K4 is the largest complete planar graph. The link provided discusses the duality between graphs and Voronoi diagrams and how it can be used in this proof.
  • #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 ?
 
Last edited:
Physics news on Phys.org
  • #2
Last edited:
  • #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
 

Related to Planar graphs with minimum degree

1. What is a planar graph with minimum degree?

A planar graph with minimum degree is a type of graph where every vertex has at least a specified minimum number of edges connected to it. In other words, the minimum degree is the smallest number of edges incident to any vertex in the graph.

2. How do you determine the minimum degree of a planar graph?

To determine the minimum degree of a planar graph, you need to count the number of edges incident to each vertex and then find the smallest number. This will be the minimum degree of the graph.

3. What is the significance of minimum degree in planar graphs?

The minimum degree in planar graphs is important because it helps determine the complexity and connectivity of the graph. A higher minimum degree means that the graph is more connected and has more edges, while a lower minimum degree means that the graph is less connected and has fewer edges.

4. Can a planar graph have a minimum degree of 0?

Yes, a planar graph can have a minimum degree of 0. This means that there are some vertices in the graph that do not have any edges connected to them, and the graph is not fully connected. However, the graph can still be planar as long as it can be drawn on a plane without any edges crossing.

5. How does the minimum degree affect the coloring of a planar graph?

The minimum degree of a planar graph can affect the minimum number of colors needed to properly color the graph. This is because the minimum degree determines the number of adjacent vertices that need to have different colors. A higher minimum degree may require more colors, while a lower minimum degree may allow for fewer colors to be used.

Similar threads

  • Introductory Physics Homework Help
Replies
20
Views
1K
  • Introductory Physics Homework Help
Replies
1
Views
519
Replies
1
Views
1K
  • General Math
Replies
21
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Replies
1
Views
1K
  • Introductory Physics Homework Help
Replies
7
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Introductory Physics Homework Help
Replies
5
Views
1K
Replies
7
Views
2K
Back
Top