Paragraph

Try a proof by contradiction and consider a spanning tree of the graph.