Planar graphs with minimum degree

AI Thread Summary
A graph G with a minimum degree of 5, where only one vertex has this degree, cannot be planar. The reasoning is that attempting to draw the graph leads to the need for infinitely many vertices to accommodate all edges, resulting in crossings. The minimum number of vertices required is eight, making it impossible to create a planar representation. The discussion also references the concept of dual graphs and the geometric duality as part of the proof strategy. Ultimately, the conclusion is that the graph cannot be drawn without crossings, confirming its non-planarity.
JaeSun
Messages
37
Reaction score
0
ok, here is the question:

Let G be a graph with minimal degree \delta(G) = 5, but suppose there exists only one vertex v\in V_{G} such that d(v) = \delta(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 K_{4}, 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
 

Thread 'Struggling to understand the concept of this question (ice cube in water optics question)'

TL;DR Summary: I came across this question from a Sri Lankan A-level textbook. Question - An ice cube with a length of 10 cm is immersed in water at 0 °C. An observer observes the ice cube from the water, and it seems to be 7.75 cm long. If the refractive index of water is 4/3, find the height of the ice cube immersed in the water. I could not understand how the apparent height of the ice cube in the water depends on the height of the ice cube immersed in the water. Does anyone have an...
View full post »
Thread 'Variable mass system : water sprayed into a moving container'

Thread 'Variable mass system : water sprayed into a moving container'

Starting with the mass considerations #m(t)# is mass of water #M_{c}# mass of container and #M(t)# mass of total system $$M(t) = M_{C} + m(t)$$ $$\Rightarrow \frac{dM(t)}{dt} = \frac{dm(t)}{dt}$$ $$P_i = Mv + u \, dm$$ $$P_f = (M + dm)(v + dv)$$ $$\Delta P = M \, dv + (v - u) \, dm$$ $$F = \frac{dP}{dt} = M \frac{dv}{dt} + (v - u) \frac{dm}{dt}$$ $$F = u \frac{dm}{dt} = \rho A u^2$$ from conservation of momentum , the cannon recoils with the same force which it applies. $$\quad \frac{dm}{dt}...
View full post »

Similar threads

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

Hot Threads

Recent Insights

Back
Top