I'm working on what I'm sure is a fairly basic proof in graph theory. I must prove that
Every graph $G$ contains a path with $\delta G$ edges.
$\delta(G)$ is the minimum degree of the graph $G$.
I did ask a very premature question a few days ago about this proof, which was simply a result of my excitement. I'd like to revisit the problem now that I've had some time to think.
So far, my thoughts on how to show this are as follows (this is not a formal proof, just my thoughts on the order in which things need to be shown):
Let $G$ be a graph with $\delta(G)=d$ and with an arbitrary number of components, possibly one.
Consider the smallest possible component in graph $G$. It will have a vertex $v_i$ of degree $d$, and its neighbourhood $N_G (v_i)$ will consist of $d$ distinct vertices, all of degree $d$. So there are $d+1$ vertices of degree $d$. This is a complete graph of order $d+1$.
Let the vertices in this component be $v_1, v_2,...,v_d,v_{d+1}$.
Because these vertices are all connected to one another, there will exist an edge $e_1$ that connects $v_1$ and $v_2$, another edge $e_2$ that connects $v_2$ to $v_3$ etc. until we reach the edge which connects $v_d$ to $v_{d+1}$.
So we have a walk from $v_1$ to $v_{d+1}$:
$v_1,e_1,v_2,e_2,...v_d,e_d,v_{d+1}$
This implies a path from $v_1$ to $v_{d+1}$ (noting that $v_1\neq v_{d+1}$) and there are $d$ edges in this path $=\delta(G)$.
It follows that larger components of $G$ will still contain a path of length $\delta(G)$.
Is there anything I have overlooked? Are there any errors in my logic? It all makes perfect sense in my head but I'm worried that there may be some oversights in my steps above and I'm worried that the steps above won't make for a tight, neat proof. I'm all about the tight, neat proofs! Any feedback will be well-received. Thanks for your time, all.
I'm not too sure what the etiquette is on Math SE regarding answering old questions but I stumbled across this question and felt it would be good to drop an answer for future users that happen to ask the same question in the future.
Anyways, I'm going to do the particular case when $\delta(G) = 3$ and show that there exists a path of at least length 3. This can easily be generalized to $\delta(G) = n$ for any positive integer $n$.
So suppose $\delta(G) = 3$, then there exists a vertex $v_0$ such that $d(v_0) = 3$ (where $d(v)$ denotes the degree of a vertex $v$). Since $d(v_0)=3$, it has $3$ neighbors. Pick any neighbor and call it $v_1$. Notice that $d(v_1) \geq \delta(G) = 3$ so $v_1$ has at least three neighbors. Pick any neighbor of $v_1$, say $v_2$, such that $v_2 \neq v_0$ (which is possible since there are three neighbors to pick from). Similarly, $v_2$ has at least $3$ neighbors and it's possible to pick a neighbor of $v_2$, say $v_3$, such that $v_3 \notin \{v_0,v_1\}$. Thus you have the path, $$ v_0 \to v_1 \to v_2 \to v_3$$ which is of length 3 as desired.