• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q1SE

Expert-verified Found in: Page 805 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # 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).

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.

See the step by step solution

## Step 1: General form

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

Definition of rooted tree: A rooted tree is a 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.

## Step 2: 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. ### Want to see more solutions like these? 