Final answer:
The statement that every connected graph with order n and size m has exactly m-n+1 cycles can be proven using mathematical induction, considering the number of edges and vertices and the relation to the number of cycles that form with the addition of edges beyond those needed for a tree.
Step-by-step explanation:
To prove that every connected graph of order n and size m has exactly m-n+1 cycles, we can use mathematical induction on the number k = m-n+1. The base case starts with k = 0, which corresponds to a tree (a connected graph with no cycles). Since a tree has m = n-1 edges, it follows that when k = 0, the graph indeed has 0 cycles.
Now, assume for induction that any connected graph with m' edges (m' < m), n' vertices (n' ≤ n), and k' = m'-n'+1 cycles satisfies the statement. When we add one edge to such a graph without increasing the number of vertices, one cycle is formed. That is, for every new edge added beyond n-1, there is exactly one new cycle created.
So, if our graph has m edges and n vertices, with k = m-n+1, by the induction hypothesis, k-1 edges contributed to k-1 cycles. The m -th edge will form the k-th cycle, thus proving that the original statement holds and the connected graph has exactly m-n+1 cycles.