1
$\begingroup$

I am faced with this question.

Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$ - that is, a sequence of $k+1$ distinct vertices $v_0, v_1, ..., v_k$ such that for $0 ≤ i < k$, $v_i$ is connected to $v_{i+1}$ in $G$.

I started attacking it this way:

If $G$ has a vertex of degree atleast $k$, it has atleast $k+1$ vertices. That is, $G$ can have $|v| \geq k+1$

In the case where $|v| = k+1$, the graph is a fully connected graph of $k+1$ vertices, which trivially has a path of length $k+1$.

I am not able to prove the cases where $|v| \geq k+2$

$\endgroup$
1
  • $\begingroup$ If $P$ is a maximal path, where do all the neighbors of the endpoint vertices need to go? $\endgroup$
    – Louis
    May 1, 2014 at 22:17

2 Answers 2

3
$\begingroup$

Hint. Build up the path, using the minimum degree condition to show that you can extend it as much as you need to.

$\endgroup$
2
$\begingroup$

Here are some tips on how to approach this kind of question. First, try some example graphs, to see what happens. Pick a few small graphs, and try by hand to find such a path. What strategy do you find yourself using? Can you generalize it?

Next suggestion: Have you considered what happens if you run depth-first search in such a graph?

$\endgroup$
1
  • 3
    $\begingroup$ It's also often instructive to try to find a graph that would make the theorem false: in this case, try to construct a graph of minimum degree $k$ that contains no $k$-path. $\endgroup$ May 1, 2014 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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