Reference no: EM13965759

Explain these by drawing the graphs.

1- Let a, b, and c be positive integers with a≤b≤c. Prove that there exists a graph G with k(G)= a, k1(G)= b, δ(G)= c.

Theorem:
For that graph G,k(G)≤k1(G)≤δ(G).

Where k(G) 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).

k1(G) 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

δ(G) is the minimum degree of G .

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

Theorem:

If G is a connected graph with 2k odd vertices (k ≥1), them E(G) can be partitioned into subsets E1,E2,E3...Ek so that for each i, (Ei) 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 Ei, 1≤i≤k where each subgraph (Ei) is a cycle.