1
$\begingroup$

Can someone please verify the proof I just wrote, or offer suggestions for improvement? Also, how do I prove the base case?

Let $H$ be a simple graph on $n$ vertices that has $m$ edges. Prove that $H$ contains at least $m-n+1$ cycles.

We can proceed by induction on $m$, the number of edges. Clearly, the statement is true for all $m < n$. Suppose the statement is true for some $m \geq n$. Consider a graph $G$ with $n$ vertices and $m+1$ edges. By the inductive hypothesis, $G-e$ has at least $m-n+1$ cycles. If it has more than $m-n+1$ cycles, we are done, as $G$ will have at least $m-n+2$ cycles. Suppose, instead that $G-e$ has exactly $m-n+1$ cycles. Pick a cycle $C$ of $G-e$ and pick an edge $e'$ of that cycle.

Again, by the inductive hypothesis, $G-e'$ has at least $m-n+1$ cycles. If it has more than $m-n+1$ cycles, we are done. If, instead, it has exactly $m-n+1$ cycles, then there must be a cycle $C'$ not in $G-e$ (otherwise $G-e'$ would have only $m-n$ cycles). But then, $G$ has at least $m-n+2$ cycles, of which $m-n+1$ are in $G-e$, and one of which is in $G-e'$ and not $G-e$.

This completes the proof.

$\endgroup$
1
$\begingroup$

The proof is incorrect, though the idea is correct. The base case is missing ($m=n$), since your inductive step assume that the previous case have a cycle, so $m<n$ does not work as a base case.

However, may I suggest a simplification?

Once you got a graph with $m+1$ edge, simply use the fact that there is at least 1 cycle (since $m+1\geq n$ and maximum edge in cycleless graph is $n-1$, a fact you probably use in your base case anyway), to pick out edge $e$ in a cycle $C$. Then $G-e$ have $m-n+1$ cycle, and now add in the cycle $C$ (which is not in $G-e$ since it contains $e$) to complete the induction.

$\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.