Purchase Solution

Graphs, Digraphs, Trees and Forests

Not what you're looking for?

Ask Custom Question

I am posting one problem from Exercise 2.2, I need answer for 2.9.

I am posting another question from Exercise 3.1:

Problem 3.2.) Prove that a graph G is a forest if and only if every induced subgraphs of G contains a vertex of degree at most 1.

Problem 3.1) Draw all forests of order 6.

See attached file for full problem description.

Purchase this Solution

Solution Summary

Graphs, Digraphs, Trees and Forests are investigated in the following posting.

Solution Preview

3.1 )) Attached figures of Forests of order 6.
3.2 ))
Need to prove in both directions
Here we need to prove
Every induced subgraphs of G contains a vertex of degree at most 1 => G is a forest -- (1)

This is same as saying that
"If G is not a forest ==> Not all induced subgraphs have a vertex of degree at most 1." -- (2)

( The above fact follows from logic and this method of proof is known as proof by contrapositive.)

So let us assume that G is not a forest. Therefore there is a cycle in G. Consider the vertices of the cycle. Now consider the induced subgraph on the vertices. This graph ...

Purchase this Solution

Free BrainMass Quizzes
Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.