# Prove that there exists a path in G of length K

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?

-

## 1 Answer

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....

-
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. –  WiseStrawberry May 30 '13 at 16:31
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? –  WiseStrawberry May 30 '13 at 16:34
$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. –  N. S. May 30 '13 at 16:36
OH I get it because the WORST case scenario is where each consequent vertex is connected to a previous one. I Love it! –  WiseStrawberry May 30 '13 at 16:36