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

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

A graph is outerplanar if it can be embedded in the plane so that every vertex lies on the boundary of the exterior region. Prove the following:
If G = G(p, q) is outerplanar with p >= 2, then q <= 2p - 3.

A) Show that every bipartite graph G is a subgraph of a -regular bipartite graph.
b) Show that every bipartite graph G is of class one , that is,
What does -regular bipartite graph mean?
Can you draw a graph for me please?

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 outerplana

Question for 8.1:
Let G be a simple graph. Show that the relation R on the set of vertices of G such that uRv if and only if there is an edge associated to {u,v} is a symmetric, irreflexive relation on G.
Question for 8.2:
Show that a simple graph with at least two vertices there must be 2 vertices that have the same de

Consider the sets A0 := {0, 1, 4}, B0 := {0, 2, 8}. Consider the sets Ai := A0 + i := {i, i + 1, i + 4} ,and
Bi := B0 + i := {i, i + 2, i + 8}, for i = 1, 2, . . . , 12. All addition here is performed modulo 13. Consider the bipartite graph G whose vertices are the sets A := {Ai : 0 <= i <= 12} and B := {Bi : 0 <= i <= 12} (so

1. Find the maximum flow and the associated minimum capacity cut for the following network, by using flow augmenting path algorithm (in the order of "first labeled, first scannred"). *see attachment for diagram*
2. A maximum capacity flow augmenting path is an augmenting path such that we can increase the flow of the network

For this question, let G = K9,10:
(a) The number of vertices in G is
(b) The number of edges in G is
(c) The number of components in G is
(d) The number of hamiltonian cycles in G is
(e) λ(G) =
(f) k(G) =
Confusing in part e and f. plz show all you work and answer. thx

An undirected graph is bipartite if its nodes may divided into two sets so that all edges go from a node in one set to a node in the other set. Show that a graph is bipartite if and only if it doesn't contain a cycle that has an odd number of nodes.
See attached file for full problem description.