Problem
COM-B2-M04-P003 Endpoint of a Longest Path
#3
★★☆☆☆ Level 2 of 5
In a finite graph, a path of maximum length \(v_1v_2\ldots v_k\) is chosen. Prove that every neighbour of \(v_k\) already belongs to this path.
If there is a neighbour outside the path, what can be done to the path?
Suppose \(v_k\) is adjacent to a vertex \(u\) outside the path. Then \(v_1v_2\ldots v_k u\) is a path with one more vertex.
This contradicts the choice of the original path as a longest path. Therefore all neighbours of \(v_k\) lie on the path.
This is a key lemma for several later problems.