Paths and connectivity of graphs I am trying to show that for a graph on $n\ge 3$ vertices with minimum degree of all vertices $\ge k/2$, G connected that G has a path of length k.
I know if n is greater than k but n/2 is less than or equal to the minimum degree then I can use Dirac's theorem. However what if n/2 is greater than the minimum degree?
Further why is it necessary for k=n and G to be connected? Can it be true without both of these conditions?
 A: I think I have an answer for this, though it isn't too pretty.
Let $P$ be a path of maximum length.  By way of contradiction assume that $|P| < k$.  Our goal is to extend the path $P$ by one vertex, contradicting the fact that $P$ was of maximum length, which would give that $|P| \geq k$.
Let $a$ and $b$ be the two endpoints of $P$.  We will consider vertices closer to $a$ along $P$ as being "farther left" and vertices closer to $b$ as being "farther right".  Let $s$ be the vertex with neighbors outside of $P$ that is farthest right.  Such a $s$ must exist since $G$ is connected and hence $P$ cannot be its own connected component.  Let $q$ be the vertex to the immediate right of $s$ (notice $s \neq b$, since if $b$ had neighbors outside of $P$ we could immediately extend the path).
I claim that there exists $u, v \in P$ such that $a$ is adjacent to $u$, $q$ is adjacent to $v$, and $u$ is closer to $s$ than $v$ along $P$.  Here is why:  not counting its adjacency with $s$, $q$ has at least $k/2 - 1$ neighbors in $P$.  For each neighbor of $q$ in $P$ besides $s$, there is a vertex one step closer to $s$ that would make a valid candidate for $u$.  The vertex $a$ must have $k/2$ neighbors in $P$ (since otherwise we could extend $P$ to make a longer path, a contradiction).  Thus, if there is no such $u, v \in P$, then $a$ has $k/2$ neighbors which are disjoint from the $k/2-1$ candidates for $u$.  This makes a total of $k/2 -1  + k/2 = k - 1$ vertices in $P$ besides $a$ itself -- a contradiction.   Therefore, there is such a $u$ and $v$.
Given such a $u$ and $v$, we can then extend $P$ to include one more vertex, which finishes the proof.  How?  Well, start at $b$, and head left towards $q$.  You'll either reach $q$ first or $v$ first.  If you reach $v$ first, then go to $q$ and head right towards $u$, then jump to $a$, head right and reach $s$.   If you hit $q$ first, then jump to $v$, head towards $a$, jump to $u$, then go to $s$.  Once you've reached $s$, you can then extend the path one more vertex which completes the proof.

