0 votes
32 views
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex os repeated. The $length$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle).

Let $G$ be an undirected graph with minimum degree $k \geq 2$.

Show that $G$ contains a simple path of length at least $k$.
asked in Others | 32 views
0

this question contains part b

## 1 Answer

0 votes
Suppose there exists a graph with longest path of $m < k$ from $v_1, v_2,....,v_{m+1}.$

$v_{m+1}$ is the last vertex of the path that means there is no other vertex in the graph that is not already included in the path. This means if $v_{m+1}$ is connected to all the vertices of the path then too deg($v_{m+1}$) $< k$, this contradicts our assumption that each vertex having degree $k > m$.
answered by Boss (29.6k points)

0 votes
1 answer
1
0 votes
0 answers
2
0 votes
1 answer
3
+1 vote
2 answers
4
0 votes
1 answer
5
0 votes
2 answers
6
0 votes
0 answers
7