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.© BrainMass Inc. brainmass.com June 19, 2018, 9:58 pm ad1c9bdddf
3.1 )) Attached figures of Forests of order 6.
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 ...
Graphs, Digraphs, Trees and Forests are investigated in the following posting.