Question

Suppose that H is a connected graph that contains a proper cycle. Argue that removing any single edge from this cycle will leave a subgraph of H that remains connected.

Make sure you are fully addressing the technical definitions involved --- do not just talk vaguely about vertices being connected, you need to discuss specific paths between vertices.

Answer 1

Let G be a connected graph which contains a cycle C.Let H be the graph subgraph of G by eliminating one edge e from the cycle C of the graph G.Let u,v be two vertices of the graph H.Since G is connected and u,v are two vertices of the graph G then there is a path P between u and v.If the path P does not contain e then P is a path in H if P contains the edge e then we prove that H is still connected.Let e=u1v1.Since u1,v1 lies on the cycle there is another path Q joining u1 and v1.Let P1 be a path joining u , u1 and P2 be a path joining v1,v.Clearly the path P1 and P2 does not contain the edge e,therefore P1+Q+P2 is a path in H joining u and v.Hence H is connected.