Purchase Solution

Outerplanar and Bipartite Graphs

Not what you're looking for?

Ask Custom Question

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.
from:
http://en.wikipedia.org/wiki/Planar_graph

Purchase this Solution
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.

Solution Preview

We need to prove two statements:

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

and

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

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

Solution provided by:
Changping Wang, MA
Education
  • BSc , Wuhan Univ. China
  • MA, Shandong Univ.
Recent Feedback
  • "Your solution, looks excellent. I recognize things from previous chapters. I have seen the standard deviation formula you used to get 5.154. I do understand the Central Limit Theorem needs the sample size (n) to be greater than 30, we have 100. I do understand the sample mean(s) of the population will follow a normal distribution, and that CLT states the sample mean of population is the population (mean), we have 143.74. But when and WHY do we use the standard deviation formula where you got 5.154. WHEN & Why use standard deviation of the sample mean. I don't understand, why don't we simply use the "100" I understand that standard deviation is the square root of variance. I do understand that the variance is the square of the differences of each sample data value minus the mean. But somehow, why not use 100, why use standard deviation of sample mean? Please help explain."
  • "excellent work"
  • "Thank you so much for all of your help!!! I will be posting another assignment. Please let me know (once posted), if the credits I'm offering is enough or you ! Thanks again!"
  • "Thank you"
  • "Thank you very much for your valuable time and assistance!"
Purchase this Solution
Free BrainMass Quizzes
Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

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.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Probability Quiz

Some questions on probability

View More Free Quizzes
Related BrainMass Solutions

  • Trees and Graphs : Outerplanar Graphs

    Here is an example of outerplanar graphs. You can see every vertex is on the boundary (red cycle) of the exterior region. Trees and outerplanar graphs are investigated. Sign representations for minimum degrees are determined.

  • Outerplanar Graphs

    Outerplanar graphs are investigated. The solution is detailed and well presented.

  • Bipartite Graphs

    Bipartite Graphs are investigated.

  • Graphs : Coloring Maps

    Therefore G* is a bipartite graph. Note that every graph is bipartite if and only if it has chromatic number 2. And every dual of bipartite graph is Euler graph and every Euler graph having vertex of even degree.

  • Discrete math - graphs and relations

    This provides examples of a few different topics, including simple graphs, Hamilton circuits, bipartite graph, relations, and binary trees.

  • Flow Augmenting Path Algorithm, Bipartite Graph and Cardinality

    35717 Flow Augmenting Path Algorithm, Bipartite Graph and Cardinality 1.

  • Automata and Computability

    Therefore, BIPARTITE  NL. The expert examines automata and computability.

  • outerplannar graph

    378118 Use the four color theorem Use the four color theorem to prove that every outerplanar graph is 3-colorable. Please see the attached document. The coloring of the vertices is assessed.

  • Bipartite graph matching proof

    This provides an example of a proof regarding a bipartite graph and matching.

View More Related Solutions