StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q1SE

Expert-verifiedFound in: Page 805

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.

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.

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.

94% of StudySmarter users get better grades.

Sign up for free