8
$\begingroup$

A path in a graph is a subgraph isomorphic to $P_n$, for some $n$. The length of a path is its number of edges. Prove that every graph $G$ has a path of length $\delta(G)$, where $\delta(G)$ is the minimum degree of $G$.

$\endgroup$

closed as not constructive by Andrés E. Caicedo, Micah, Lord_Farin, Joe, Dennis Gulko Apr 25 '13 at 16:41

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Also, I think it's impolite to disregard suggestions on how to improve your question (such as those here). $\endgroup$ – Douglas S. Stones Apr 23 '13 at 14:12
4
$\begingroup$

I hope its a simple graph. Let $P$ be the maximal path in the graph $G$. On the contrary assume $|P|\le\delta(G)$.

Suppose $v\in V(P)$ be an endpoint in the path. As $v$ is adjacent to $\delta(G)$ vertices. All of its neighbours can't be in the path $P$. But then its contradicts the fact that its the maximal path.

Hence $|P|\ge\delta(G)+1$.

$\endgroup$
  • 3
    $\begingroup$ I think you need to choose $v$ to be the end vertex of the path. $\endgroup$ – Easy Apr 23 '13 at 11:49
  • $\begingroup$ Yeah, I edited it. $\endgroup$ – Grobber Apr 23 '13 at 11:57
  • 1
    $\begingroup$ I wish people wouldn't answer questions, when the person asking the question has put in no effort beyond copying the question out of a problem set. $\endgroup$ – Gerry Myerson Apr 23 '13 at 13:31
4
$\begingroup$

Let $P$ be the longest path in $G$ from $v_0$ to $v_k$. As min degree is $\delta(G)$, this path contains every neighbor of $v_k$ are on this path and if it is not like this, then let us assume that there is a vertex $v_j$ neighbor of $v_k$ not in the path. then add this to the given path. and thus we get a path of longer length than $P$. A contradiction

$\endgroup$
  • 2
    $\begingroup$ I wish people wouldn't answer questions, when the person asking the question has put in no effort beyond copying the question out of a problem set. $\endgroup$ – Gerry Myerson Apr 23 '13 at 13:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.