Question

prove by induction that for any simple connected graph G, if G has exactly one cycle then G has the same number of edges and nodes

Answer 1

Note that a cycle has same number of edges and nodes. Therefore, we are assuming that the graph has edges outside the cycle (i.e. there are edges which are not in the cycle). Now consider a graph with 3 vertices. If it has only 1 cycle, then the graph would be a cycle and thus will have same number of edges and vertices.

Now let us assume that for any simply connected graph which have exactly 1 cycle and n-1 vertices (n>3), it has same number of edges and vertices. Then, consider a graph G with n vertices which has exactly 1 cycle. Now, let us choose an vertex of degree 1, say v, in G (we can find such vertex because if not, then all vertex lies in the cycle which proves the statement). Then G\v would be a simply connected graph with n-1 vertex and exactly 1 cycle. Thus G\v would have n-1 edges. Since v has degree 1, hence G would have n-1+1 = n edges. Thus G has same number of edges and nodes. Hence by the Principle of Mathematical induction,

for any simple connected graph G, if G has exactly one cycle then G has the same number of edges and nodes.