The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
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 (116k points) | 40 views

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 (35.4k 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
49,443 questions
53,648 answers
70,908 users