Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

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 by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

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.

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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).

Step by Step Solution

Step 1: General form

Step 2: Proof of the given statement

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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).

Step by Step Solution

Step 1: General form

Step 2: Proof of the given statement

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths