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.

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

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.

View More Free Quizzes
Related BrainMass Solutions

  • Graphs and Digraphs : Edge-Connectivity

    The expert provides graphs and digraphs for distinct nonadjacent vertices. An edge-connectivity proof is provided.

  • Forests and Eulerian Graphs

    145701 Forests and Eulerian Graphs Let F be a forest. Add a vertex x to F and join x to each vertex of odd degree in F.

  • conservation of Old Growth forests in the Pacific Northwest

    Large trees tend to grow over long spans of time, and so are more scarce than smaller trees.

  • Discussing the Productivity of Forests

    A century or more can pass before half of all trees die and are replaced with new growth. On the other hand tropical rain forests occur in tropical climates with abundant precipitation and no seasonal drought.

  • Ecosystem Succession

    An example that comes to mind is the forests of the southwest, which have been affected by pine beetles and forest fires. Forest fires can be natural or caused by humans.

  • Difference between conservation and preservation as it affect the forests.

    In the past, people would devastate a forested area and then move on. Conservation is aimed at using forests more like a 'farm' if you will-taking only mature trees and replanting after those are taken.

  • natural ecosystem in which you live

    But due to the location of the lake and heavy industrialization with demand for timer, a large number of trees were cut down and the lake became a small pond. Globally, tropical forests are considered to be carbon sinks.

  • Graph proofs

    This provides examples of working with proofs regarding graphs and nonisomorphic graphs.

  • Outerplanar Graphs

    As H is a planar graph with p+1 vertices and p+q edges, by a known result (Theorem 6.3 on page 156, Graphs and Digraphs, third edition, G. Chartrand and L.

View More Related Solutions