Show that G has a path of $\delta(G)$ for minimum degree greater than 2

Asked Sep 09 '17 at 21:46

Active Sep 10 '17 at 17:01

Viewed 517 times

Let G be a graph with minimum degree $\ge2$. The minimum degree of G is denoted by $\delta(G)$

Show that G has a path of $\delta(G)$

Ok first we know that the graph must at least be a triangle cycle because the minimum degree is greater than 2.

So let P be a be a max path from $v1,v2,...,vk$ it must have all of the neighbors of v1 to be a max path and all the neighbors of v1 are $\delta(G)$

Hence the max path must be $P=\delta(g)+1$ the one is the graph the plus 1 coming from the $v1vk$ edge the final edge.

I am not sure this is true I am new to the graph theory.

edited Sep 10 '17 at 17:01

asked Sep 09 '17 at 21:46

Fernando Martinez

I assume your sentence "Prove that the cirucumference of a graph denoted..." is incomplete? – JRyan Sep 10 '17 at 07:19
Probably it is not necessary that a maximal path contains all neighbors of $v_1$. – Alex Ravsky Sep 10 '17 at 08:46
Just copied from the Related tab: Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$. – Alex Ravsky Sep 10 '17 at 08:49
Oh yeah I the circumference of a graph I deleted that part I made a mistake there. – Fernando Martinez Sep 10 '17 at 17:01

0 Answers0