Prove that in a connected graph G with p vertices q edges an

Prove that in a connected graph G with p vertices,  q edges, and at least one cycle,  q greaterthanorequalto p.

Solution

For a connected graph, G(p,q), if there are no cycles, then number of vertices is one more than the number of edges, ie, p=q+1.

Proof by induction:

If p = 1 (ie, there is only one vertex), then there is no edge, that is q = 0, Hence p = q+1

Assume that for p = n, q = n-1.

For p = n+1, if we add a vertex, in a connected graph, then we need to add an edge to connect that vertex. Therefore q = n-1+1 = n. Hence, p = q+1

Hence, proved.

Now, if the graph contains cycles, then for the same number of vertices, the number of edges increases. So, if there is one cycle, there is one more edge than the number of edges in the graph without cycles.

Hence, q = p-1 + 1 = p.

Now, if we increase the number of cycles for same number of vertices, then the number of edges increase, ie, q>p.

Hence, proved.