Question

Show that a simple graph is a tree if and only if it contains no simple circuits and the addition of an edge connecting two nonadjacent vertices produces a new graph that has exactly one simple circuit (where circuits that contain the same edges are not considered different).

Short answer

Therefore, the given statement is true. Let T be the tree, e be the edges and u and v be the vertices. Then, a simple graph is a tree if and only if it contains no simple circuits and the addition of an edge connecting two nonadjacent vertices produces a new graph that has exactly one simple circuit been the true statement.

Step-by-step solution

General form 

Definition of tree: A tree isa connected undirected graph with no simple circuits.

Definition of rooted tree: A rooted tree isa tree in which one vertex has been designated as the root and every edge is directed away from the root.

Principle of Mathematical induction: To prove that\({\bf{P}}\left( {\bf{n}} \right)\) is true for all positive integers n, where \({\bf{P}}\left( {\bf{n}} \right)\)is a propositional function, we complete two steps:

Basis step: We verify that\({\bf{P}}\left( 1 \right)\) is true.

Inductive step: We show that the conditional statement\({\bf{P}}\left( {\bf{k}} \right) \to {\bf{P}}\left( {{\bf{k + 1}}} \right)\) is true for all positive integers k.

Proof of the given statement

Given that, circuits that contain the same edges are not considered different.

To prove: a simple graph is a tree if and only if it contains no simple circuits and the addition of an edge connecting two nonadjacent vertices produces a new graph that has exactly one simple circuit.

Suppose T is a tree.

Then clearly T has no simple circuits.

If we add an edge \({\bf{e}}\) connecting two nonadjacent vertices \({\bf{u}}\) and \({\bf{v}}\), then obviously a simple circuit is formed, because when e is added to T the resulting graph has too many edges to be a tree.

The only simple circuit formed is made up of the edges e together with the unique path in T from v to u.

Suppose T satisfies the given conditions. All that is needed is to show that T is connected, because there are no simple circuits in the graph.

Assume that T is not connected. Then let u and v be in separate connected components.

Adding \({\bf{e = }}\left\{ {{\bf{u,v}}} \right\}\) does not satisfy the conditions.

Conclusion: So, a simple graph is a tree if and only if it contains no simple circuits.

Hence proved.