1
$\begingroup$

Let $r$ be the length of the shortest cycle in a graph $G$. When does $\dfrac{r}{r-2}=\dfrac{|E|}{|V|-2}$

So far I've managed to establish, that the following equation is true for cyclic graphs $C_n$, because then $|E|=|V|=r$ so trivially it's true. But is there any other case when this is true?

$\endgroup$
1
$\begingroup$

Take for example the cycle $C_6$ and connect the vertices $1$ and $4$ by two more paths of length $3$. Then for resulting graph $r=6, |E|=12, |V|=10$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.