9
$\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$
1
  • $\begingroup$ Also, I think it's impolite to disregard suggestions on how to improve your question (such as those here). $\endgroup$ Commented Apr 23, 2013 at 14:12

2 Answers 2

7
$\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$
1
  • 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$ Commented Apr 23, 2013 at 13:31
5
$\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
  • 3
    $\begingroup$ I think you need to choose $v$ to be the end vertex of the path. $\endgroup$
    – Easy
    Commented Apr 23, 2013 at 11:49
  • $\begingroup$ Yeah, I edited it. $\endgroup$
    – Grobber
    Commented Apr 23, 2013 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$ Commented Apr 23, 2013 at 13:31

Not the answer you're looking for? Browse other questions tagged .