Explore BrainMass

Explore BrainMass

    Graphs, Digraphs, Trees and Forests

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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 March 4, 2021, 7:43 pm ad1c9bdddf
    https://brainmass.com/math/combinatorics/graphs-digraphs-trees-forests-118605

    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 in the following posting.

    $2.49

    ADVERTISEMENT