Let $G=(V,E)$ be a nonempty graph and let $d(v)\geq k$ for all $v\in V$. Prove that there exists a path in $G$ of length $k$.

Alright so my first intuition is $$\sum_{i=1}^{n} d(v_i) \geq nk \quad(n=|E|)$$

So a path contains each vertex once and has no cycle. Seeing as each vertex has a degree $\geq k$, in the worst situation (because this limits the length of our path) we have: $$\sum_{i=1}^{n} d(v_i) = nk$$

We also have $\sum_{v\in V} d(v_i) = 2|E|$, so $$ 2|E| = nk. $$

This seems logical but I cant translate this into the length of a path. Any tips? edit maybe we can say because we have $\frac{nk}{2}$ edges, and $n$ vertices, we could maybe use induction?


Hint. Pick a vertex $v_1$. It is connected to $k$ vertices. Pick one of them $v_2$, this is connected to $k$ vertices, and $k-1$ of them are not in the path (only $v_1$ can be).

$v_2$ is connected to at least $k-2>0$ vertices not in the path. Pick one of them, $v_3$ repeat....

Induction by $k$ is probably the simplest way to write the solution....

  • $\begingroup$ I understand why induction is the way to go, but I'm having trouble formulating the base step. Let me work on it a bit. $\endgroup$ – WiseStrawberry May 30 '13 at 16:31
  • $\begingroup$ I wrote down take $v_1$ as your starting vertex, you can choose from $k$ edges to continue your path. The next vertex $v_2$ should have $k-1$ useable paths (no vertex can be visited twice) and so on until $v_k$ where it has $(k-k)$ useable verteces. But my problem is after $v_3$ because it can also have $k-1$ edges to pick from right? $\endgroup$ – WiseStrawberry May 30 '13 at 16:34
  • 3
    $\begingroup$ $v_3$ is connected to $k$ vertices. One of them is $v_2$, another one MIGHT be $v_1$, but there are at least $k-2$ vertices which are not $v_1,v_2$ or $v_3$. Just pick one of them at random. $\endgroup$ – N. S. May 30 '13 at 16:36
  • 1
    $\begingroup$ OH I get it because the WORST case scenario is where each consequent vertex is connected to a previous one. I Love it! $\endgroup$ – WiseStrawberry May 30 '13 at 16: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.