Explore BrainMass

Outerplanar and Bipartite Graphs

A graph is outerplanar if it can be embedded in the plane so that every vertex lies on the boundary of the exterior region.

A graph G is outerplanar iff G + K_1 is planar.

Note:A bipartite graph (i.e., a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent) such that every pair of graph vertices in the two sets are adjacent. If there are p and q graph vertices in the two sets, the complete bipartite graph (sometimes also called a complete bigraph) is denoted K_p,q.

K_1 is the complete 1-graph
K_3,3 is the complete bipartite graph with 3 vertices in each disjoint vertex set.

also:In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. A nonplanar graph cannot be drawn in the plane without edge intersections.

Solution Preview

We need to prove two statements:

(1) If a graph G is outerplanar, then G + K_1 is planar;


(2) If G+ K_1 is planar, then G is outerplanar.

Proof of (1): By the definition of being outerplanar: A graph is ...

Solution Summary

Outerplanar and Bipartite Graphs are investigated. The solution is detailed and well presented. The response was given a rating of "5/5" by the student who originally posted the question.