Prove that $G$ has at least $q-p+c$ cycles.

Question

I need your help with this question:

Suppose that a graph $G$ has $p$ vertices, $q$ edges, and $c$ components.

Prove that $G$ has at least $q-p+c$ cycles.

I don't know how to prove that.

Answer 1

A connected graph without cycle has $n$ nodes, $n-1$ edges, and it's called a tree.
If the number of edges is less then $n-1$, it is disconnected, if it's more then $n-1$, it has a cycle. Moreover, the number of circle is at least #edges - #nodes + $1$.
This is easily proved by induction, noticing that adding an edge to a connected graph, increases the number of his cycles at least by one.

Keeping this in mind, you can count for each component a lower bound for the cycles.

If $a_1,\dots, a_c$ is the number of nodes in each component, and $b_1,\dots, b_c$ the number of edges, you have that the number of cycles is at minimum $$ \sum b_i-a_i+1=q-p+c $$

Answer 2

Start with the empty graph (no edges) on $p$ vertices; so $q=0$, $c=p$, $q-p+c=0$. Now draw the edges one by one. Each time you add an edge, either the new edge joins vertices in two different components, so $q$ increases by one, $c$ decreases by one, $q-p+c$ is unchanged; or else the new edge joins two vertices in the same component, $c$ is unchanged, $q$ increases by one, and you get at least one new cycle containing the new edge. You can write this as a proof by induction on the number of edges.

Answer 3

Consider a spanning forest $T$ of $G$. Since $T$ has $p$ vertices and $c$ components, then $T$ has $p-c$ edges. We know that adding a new edge to any component of $T$ creates at least one cycle. Repeatedly add new edges until we obtain the graph $G$. We know that the size of $G$ is $q$ and that the size of $T$ is $p-c$, so we added $q-(p-c)=q-p+c$ new edges and since each edge creates at least one cycle we know that $G$ contains at least $q-p+c$ cycles.

Answer 4

If $G$ has a cycle $C$, then we remove one of the edges on $C$, and deduce the result by induction (on $q$). Otherwise, $G$ is a forest, and then the result follows because a tree on $v$ vertices cannot have $v$ edges.