The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
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 by Veteran (112k points) | 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)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,262 questions
49,758 answers
164,196 comments
65,849 users