0
$\begingroup$

Considering we have an undirected connected graph with n nodes and n+1 edges , what is the maximum number of simple cycles the graph can have ? what is the proof ?

$\endgroup$
1
  • $\begingroup$ Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be put on hold. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$ – José Carlos Santos Dec 31 '19 at 11:08
0
$\begingroup$

Remove two edges while keeping the graph connected. A connected graph with $n$ nodes and $n-1$ edges is a tree (hence without cycles). Add one of the edges, back, and you create one cycle. Add the other edge back, and you create at most $2$ more simple cycles, so the total is at most three.

$\endgroup$
2
  • $\begingroup$ Thanks , but can you explain why adding the second edge back creates at most 2 more simple cycles ? $\endgroup$ – Nazarene Christian Soldier Dec 31 '19 at 11:24
  • 1
    $\begingroup$ @NazareneChristianSoldier: Without the first edge we added, there is again only one simple cycle. So any further simple cycles must use both edges. Assume there are two simple cycles that use both edges. Then we can combine parts of them to form a (not necessarily simple) cycle that contains neither of them, contradicting the fact that the graph without them is a tree. $\endgroup$ – joriki Dec 31 '19 at 11:30

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.