Share
Explore BrainMass

Drawing Partitioned Graphs

Please explain these by drawing the graphs.
1- Let a, b, and c be positive integers with Prove that there exists a graph G with
Theorem:
For that graph G, .

Where is the vertex-connectivity,(is the minimum cardinality of a vertex-cut of G if G is not complete, hence it is the minimum number of vertices whose removal results in a disconnected or trivial graph).
is the edge-connectivity of a graph G which is the minimum cardinality of edge-cut of G if G is nontrivial, hence it is the minimum number of edges whose removal from G results in a disconnected or trivial graph
is the minimum degree of G .

2. - Let G be a connected graph with 2k odd vertices, .Show that E(G) can be partitioned into subsets so that is open trail for each i. Then show that for cannot be partitioned into subsets , so that is an open trail for each i.

Theorem:
If G is a connected graph with 2k odd vertices ( ), them E(G) can be partitioned into subsets so that for each i, is a trail connecting odd vertices and such that at most one of these trails has odd length.

Theorem;
A nontrivial connected graph G is eulerian if and only if E(G) can be partitioned into subsets , where each subgraph is a cycle.

Attachments

Solution Summary

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

$2.19