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