recategorized by
499 views
1 votes
1 votes
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $\textit{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$.
recategorized by

2 Answers

1 votes
1 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$.

Related questions

1 votes
1 votes
2 answers
1
go_editor asked Dec 30, 2016
759 views
An undirected graph can be converted into a directed graph by choosing a direction for every edge. Here is an example:Show that for every undirected graph, there is a way...
1 votes
1 votes
2 answers
3
1 votes
1 votes
2 answers
4
go_editor asked Dec 30, 2016
549 views
A dodecahedron is a regular solid with $12$ faces, each face being a regular pentagon. How many edges are there? And how many vertices?$60$ edges and $20$ vertices$30$ ed...