Let $\delta$ denote the minimum degree of graph G. Show for every graph G, if G is connected and |V|>2$\delta$, then G has a path of length 2$\delta$.

I started this way:

Let P be the longest path in G. If P has length k but does not use all the vertices, I tried using this Theorem (Let G be a graph of order n$\ge3$. If deg(x) + deg (y)$\ge$ n for all pairs of non-adjacent vertices x,y, then G is Hamiltonian) to find a cycle of length k+1, and use the cycle to find a longer path.

I do not know where to go from here.


1 Answer 1


Let $P=v_1\ldots v_m$ be a path of maximal length and assume $m<|V|$. Let $S$ be the vertex set of $P$.

Note that the subgraph induced by $S$ cannot contain a cycle of length $m$: there must be a vertex $w$ that is not on this cycle and since $G$ is connected there is a shortest path from $w$ to the cycle. Now cutting the cycle next to the attachment point of this shortest path would give a path that is longer than $P$. Contradiction.

Both $v_1$ and $v_m$ must have all their neighbours on $P$ (or otherwise we can make $P$ longer), so specifically $v_1$ must have at least $\delta$ neighbours in $v_2\ldots v_m$.

Now assume $v_i$ is a neighbour of $v_m$. We claim that $v_{i+1}$ cannot be a neighbour of $v_1$: if it was, we find a cycle $v_1\ldots v_iv_mv_{m-1}\ldots v_{i+1}$, which was disallowed. So for each neighbour of $v_m$ on $P$ we find a non-neighbour of $v_1$ in $v_2\ldots v_m$.

Now we can resume: $v_2\ldots v_m$ contains at least $\delta$ neighbours of $v_1$ and at least $\delta$ non-neighbours of $v_1$. So $P$ must have at least $2\delta+1$ vertices, i.e. length at least $2\delta$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.