Question

please give me the complete prove for this question;

7. For a graph G of order n 2, define the k-connectivity Kk(G) of G (2 S k n) as the minimum number of vertices whose removal from G results in a graph with at least k components or a graph of order less than k. (Therefore, K2(G) = K(G).) A graph G is defined to be (f,k)- connected if Kk(G) . Let G be a graph of order n containing a set of at least k pairwise nonadjacent vertices. Show that if degg U2

General information:

Answer 1

If G is connected and G − W is disconnected, where W is a set of vertices, then we say that W separates G, or that W is a vertex-cut

The maximal value of k for which a connected graph G is k-vertex connected is the vertex-connectivity of G, denoted by (G). If G is disconnected, we put (G)=0

The vertex-connectivity – (G) – of a graph G is the minimum cardinality of a vertex-cut if G is not complete, and (G) = n – 1 if G = Kn for some positive integer n. κ( G ) = min { W : W ⊂ V( G ) and W is a vertex – cut

Every graph that is not complete has a vertex-cut: the set of all vertices distinct from two nonadjacent vertices is a vertex-cut.

A graph G is 2-edge-connected if it is connected, has at least two vertices and contains no bridge. (G) = 0 iff G is disconnected or trivial.

(G) =1 iff G is connected and contains a bridge

Proof’ let G be a graph of order n>=2, and let k be an integer that l<=k<=n-1, if

Deg v≥

Suppose that the theorem is false. Then there is a graph G satisfying the hypothesis of the theorem such that G is not k-vertex-connected. Since G is not a complete graph.

Then there exists a vertex-cut W such that |W | = l <k – 1. So, the graph G – W is disconnected

of order n – l

Let G1 be a component of G – W of smallest order, say n1. Thus

n1≤                     

            ≤ ≥

Let v be a vertex of G1. Necessarily, v is adjacent in G only to vertices of W or to other vertices of G1.

Hence

For k = 2 hence we assume that k ≥3.

Let W be a set of vertices of G. Among all cycles of G, let C be a cycle containing a maximum number, say l, vertices of W.

It is clear that l ≥2.

We will to show that l = k. Assume to the contrary, that l < k, and let w be a vertex of W which does not lie on C.

The C can be labeled so that C:w₁,w₂,…,w_l,w₁, where w_i ϵW for 1≤ i ≤l .

internally disjoint w–w_i paths, denoted by Qi, 1≤ i ≤l .

Replacing the edge w1w2 on C by the w₁–w₂ path determined by Q₁ and Q₂.

So, we get a cycle containing at least l+1 vertices of W, which is a contradiction. Therefore, C contains at least l+1 vertices