Question

Question 1# (a) Let G be a connected graph and C a non-trivial circuit in G. Prove directly that if an edge e fa, b is removed from C then the subgraph S C G that remains is still connected. "Directly' means using only the definitions of the concepts involved, in this case connected' and 'circuit'. Hint: If z and y are vertices of G connected by path that includes e, is there an alternative path connecting x to y that avoids e? (b) Prove that any connected graph G with n vertices and n-1 edges is a tree. You may use the converse result (that a tree with n vertices has n-1 edges) and you may also use the result of part (a). Hint: Suppose G is not a tree. Part (a) becomes applicable. Why? If S is not a tree then part (a) can be applied again and so on. Eventually we are lead to the contradiction of a 'tree' with too few edges.

Answer 1

Solution:

Part(a):

Every two vertex of a circuit is connected by two different, non-overlapping paths.

If we take only one edge out, then we are destroying one of those paths. This, we can still reroute paths which involved getting through 2 vertex of the circuit via the other path.

Part(b):

Any connected graph with n vertices and (n-1) edges is a tree.

d graph with n vertices and edges. We show that G Proof Let G be a connecte contains no cycles. Assume to the contrary that G contains cycles. Remove an edge from a cycle so that the resulting graph is again connected. Continue this process of removing one edge from one cycle at a time tll the resulting graph H is a tree. As H has n vertices, so number of edges in H is n -1. Now, the number of edges in G is greater than the number of edges in H. Son-1> n-1, which is not possible. Hence, G has no cycles and therefore is a tree.