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$
  • $\begingroup$ If $P$ is a maximal path, where do all the neighbors of the endpoint vertices need to go? $\endgroup$ – Louis May 1 '14 at 22:17
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.

| cite | improve this answer | |
$\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?

| cite | improve this answer | |
$\endgroup$
  • 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$ – David Richerby May 1 '14 at 20:36

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.