Hint
4.2.5.1
.
Try a proof by contradiction and consider a spanning tree of the graph.
in-context