Every graph G contains a path with d(G) edges (proof critique).

223 Views Asked by At

Curious to see whether my proof below is acceptable or not. Any feedback will be well received.

Many thanks.

Every graph G contains a path with $\delta(G)$ edges.

$\mathbf{Proof.}$ Let $G$ be a graph with $\delta(G)=d$, and vertex set $\{v_{1},v_{2},v_{3},...,v_{n}\}$. Now consider the neighbourhood of a vertex $v_{i}$ with degree $d$. Each distinct vertex incident to $v_{i}$ will have a degree greater than or equal to $d$. This implies that graph $G$ has at least $d+1$ vertices, one with degree $d$ and the remaining vertices with degree at least $d$. $\delta(G)$ forces graph $G$ to be connected. Because there are at least $d+1$ vertices, there will exist a path with $d+1-1=d$ edges.