Simple Graph Question

51 Views Asked by At

Consider a connected graph $G$, and let $P$ be a path of maximal length $l$. Show that if $G$ contains a cycle $C$ of length $l+1$ then $v(G)=l+1$

I didn't know where to start, any hint would be appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

Assume to contrary that $v(G)>l+1 \implies v(G) \ge l+2$ which means that there is a vertex outside the cycle $C$. Now find a path starting from this vertex and going into the cycle of length $l+1$ and that would be the contradiction.