Let be the longest simple path in the graph, and suppose (we want to get a contradiction) that .
What happens with the neighbours of ? Do they all appear in the path ?
Prove that if G is a simple graph with minimum degree k, where k 2 then G has a path of length at least k.
I've been bouncing through ideas all day but I keep finding flaws in them. I feel like I must show that G is hamiltonian but I do not know how to do that.
Any help is appreciated, plus rep like always.
So would have to be connected to at least k points(min degree). Since because r is connected to k points and then we add the r point itself. Therefore which is a contradiction of and hence G has a path length of at least k.
This makes more sense, if I'm wrong please correct me but thanks again!
PS PaulRS as in the creator of RS? :P
Well, if the path had length or less, then there'd be at most nodes in the path but then has a neighbour that is none of the others in the path, thus we would be able to extend the path (adding the new node at the end) contradicting the maximality of the length of the path.
PS: No, it's my initials.