Hey could someone please check my proof that every graph has a path of length k where k is the minimum degree of the graph.
I try to prove this by induction showing that every path with degree less than k can be extended.
First of all consider the case when the path length p = 0 starting at some vertex v0 as the base case. I know that v0 is connected to at least k other vertices therefore the path can be extended when p = 0.
I now assume this for all paths of length p between p = 0 and p = k-1. I now try to prove for the case p = k-1. For a path of length k-1 between two vertices v0 and ve I know that ve is connected to at least k other vertices. Now let's say that every other vertex in the path is connected to ve. This still leaves ve with at least two other adjacent vertices since there are k-2 other vertices in the path. Therefore a path with length k-1 can be extended. Therefore by Induction every path of length less than k can be extended and therefore there exists a path of length k.
Best Answer
You've got the right idea ! But there may be some details missing to make it entirely rigorous.
In particular, you prove the statement for $p =0$ and jump to $p = k - 1$.
A proper induction proof would consider $p = i$ for an arbitrary $0 < i < k$.
Then you need to state clearly that we can use the inductive hypothesis to find a path of length $i - 1$. And then you can adjust your argument to say that $v_e$ has at least $k - i$ free neighbors.
By the way, if your path is of length $k - 1$, $v_e$ isn't supposed to end up with 2 free neighbors. The length of a path is its number of edges. So a path of length $p$ has $p + 1$ vertices, which bounds the $v_e$ neighbors to a minimum of one.