Show that the components of a graph partition its vertex

Question

1.  Show that the components of a graph partition its vertex set. (In other words, show that every vertex belongs to exactly one component.)

Hint: Assume the contrary, and derive a contradiction.

2 .Show that every 2-connected graph contains a cycle.

Hint: Find two vertices that are linked by two independent paths.

3. Determine k(G) and λ(G) for G = P m, Cn, Kn, Km,n and the d-dimensional cube (Exercise 2); d, m, n ≥ 3.

Hint: For each type of graph, the solution requires separate proofs of (coinciding) upper and a lower bounds. For the cube, use induction on n.

4. Is there a function f : N → N such that, for all k ∈ N, every graph of minimum degree, at least, f (k) is k-connected?

Hint: Try to find counterexamples for k = 1. 

Answer 1

Answer the following graph questions by showing all the steps required to describe the answers. Q1. Illustrate that the components of a graph partition its vertex set. (In another word, describe that each and every vertex belongs to precisely one component.) Hint: Suppose the contrary and derive a negation. Q2. Explain that each and every 2-connected graph includes a cycle. Hint: Determine the two vertices which are linked via two independent paths. Q3. Find out k(G) and ?(G) for G = P m, Cn, Kn, Km,n and the d-dimensional cube; d, m, n = 3. Hint: For each and every kind of graph, the solution needs separate proofs of (coinciding) upper and lower bounds. For the cube, make use of induction on n.