Question

Show that a simple graph is a tree if and only if it is connected but the deletion of any of its edges produces a graph that is not connected.

Short answer

A connected graph with no simple circuits is called a tree. We claim that a simple graph is a tree if and only if it is connected and the deletion of any of its edges produces a disconnection.

Step-by-step solution

Assuming that a simple graph is a tree

A connected graph with no simple circuits is called a tree.

We claim that a simple graph is a tree if and only if it is connected and the deletion of any of its edges produces a disconnection.

Suppose G is a simple graph. First, assume G is a tree, then clearly G is connected and has no simple circuits. Suppose an edge (a,b) of G is deleted.

Disconnection

If G is still connected, then there is a path p from a to (a,b), the path p together with the edge (a,b) becomes a circuit, a contradiction.

Hence the deletion of any edge forms a disconnection.

Conversely, suppose G is connected and deletion of any of its edge forms a disconnection. Then, G will not have a simple circuit or otherwise the deletion of an edge would have not produced a disconnection.

Hence, G is a tree.