Share
Explore BrainMass

Graphs, Digraphs, Trees and Forests

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.

Attachments

Solution Preview

3.1 )) Attached figures of Forests of order 6.
======================================
3.2 ))
Proof:
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 ...

Solution Summary

Graphs, Digraphs, Trees and Forests are investigated.

$2.19