Planar graphs with minimum degree

Click For Summary
SUMMARY

The discussion centers on proving that a graph G with a minimum degree of δ(G) = 5, where only one vertex v has degree equal to δ(G), is not planar. The user illustrates that attempting to draw the graph leads to an infinite number of vertices being required to accommodate all edges without crossings. They reference the impossibility of drawing a complete graph with the remaining vertices and mention K4 as the largest complete planar graph, indicating that the conditions of G violate planarity. The user also suggests exploring dual graphs and Voronoi diagrams as part of the proof strategy.

PREREQUISITES
  • Understanding of graph theory concepts, particularly planar graphs.
  • Familiarity with vertex degree and its implications in graph structures.
  • Knowledge of complete graphs, specifically K4 and its properties.
  • Basic comprehension of dual graphs and Voronoi diagrams.
NEXT STEPS
  • Study the properties of planar graphs and the conditions for planarity.
  • Learn about the proof techniques involving dual graphs in graph theory.
  • Explore the concept of Voronoi diagrams and their relationship to graph structures.
  • Investigate the implications of vertex degree on graph connectivity and planarity.
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory, particularly those interested in the properties of planar graphs and proof techniques in combinatorial mathematics.

JaeSun
Messages
37
Reaction score
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
Last edited:
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
 

Similar threads

Maximum and minimum speeds in a moving cube
  • · Replies 20 ·
Replies
20
Views
2K
Undergrad Finding if a subgraph of a minimal non-planar graph is maximal planar
  • · Replies 1 ·
Replies
1
Views
2K
Python Help solving a geometrical matching issue with Graph Neural Networks
  • · Replies 1 ·
Replies
1
Views
3K
Two networks described by v-i graph: Find voltages when interconnected
  • · Replies 1 ·
Replies
1
Views
2K
Proving a graph not simple and planar after adding edges
  • · Replies 4 ·
Replies
4
Views
2K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
  • · Replies 1 ·
Replies
1
Views
2K
High School 4-colours theorem can be proved visually
  • · Replies 21 ·
Replies
21
Views
2K
Torque and Rotational Equilibrium with a slanted Rod/Cable
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad Finding the dependence of maximum vertex degree on k-colorability
  • · Replies 1 ·
Replies
1
Views
2K
Ball on a string thrown around a spool
  • · Replies 3 ·
Replies
3
Views
1K