Share
Explore BrainMass

Trees and Graphs : Outerplanar Graphs

What bound is given for X(G) by the theorem "for every graph G,
X(G)<=1+max &(G') ,where the maximum is taken over all induced subgraphs G' of G" in the case that G is
a) a tree?
b) an outerplanar graph.

Note: -&(G') this sign represent the minimum degree of G'. Yes it is that minimum
-A graph G is outerplanar if it can be embedded in the plane so that every vertex of G lies on the boundary of the exterior region. A graph G is outerplanar if and only if G=K1 is planar.A graph G is outerplanar if and only if it contains no subgraphs that is a subdivision of either k4 or k2,3.
A graph G is outerplanar of order n>=2 and size m, then m<=2n-3.
Page 145 of the book Graph and Digraph" 4ed be G Chartrand and...
What does outerplanar graph?
draw a graph please.

Solution Preview

Please see the attached file for the complete solution.
Thanks for using BrainMass.

What bound is given for X(G) by the theorem"for every graph G,
X(G)<=1+max &(G') ,where the maximum is taken over all induced subgraphs G' of G" in the case that G is
a) a tree?

Since any induced subgraph G' of a tree is a tree or a forest, we know that the minimum degree of G' is therefore 1. Hence,

So, the upper bound is 2, implying we can colour any tree by two colours.

b) ...

Solution Summary

Trees and outerplanar graphs are investigated. Sign representations for minimum degrees are determined.

$2.19