G has subgraphs h1 h2 ht with ht g and hi a subgraph

Question

Assignment 7-

1. (a) Let G be a graph on n vertices. Prove that G is connected if and only if all the non-diagonal entries of

A(G) + A²(G) + · · · + Aⁿ(G)

are non-zero.

(b) Let J_n and I_n be the n × n all 1s matrix and n × n identity matrix, respectively.

If A(G) satisfies

A²(G) = kI_n + λA(G) + µ(J_n - I_n - A(G))

for some positive integers k, λ, µ, prove G is a k-regular graph in which every pair of adjacent vertices have exactly λ common neighbors and every pair of nonadjacent vertices have exactly µ common neighbors.

2. Suppose a connected graph G, with |V (G)| ≥ 2, has no bridges. Prove the following structure theorem for G:

"G has subgraphs H₁, H₂, . . . , H_t, with H_t = G and H_i a subgraph of H_i+1 for each i, satisfying the following properties:

- H₁ is a cycle.

- H_i is obtained from H_i-1 by adding either:

• a path with its endpoints in H_i-1 and all of its other vertices not in H_i-1, or
• a cycle with exactly one vertex in H_i-1 and all of its other vertices not in H_i-1."

3. A connected graph G is 2-connected if for any v ∈ V (G), G\v is connected. Prove that if G is a connected graph with |V (G)| ≥ 3, then G is 2-connected if and only if for every pair of vertices u, v ∈ V (G), there is a cycle containing u and v.

4. If T is a tree with |V (T)| = n, then by the Handshake Lemma we know X

∑_{v∈V (T)} deg(v) = 2(n - 1).

Prove the converse, in the sense that, if n ≥ 2 is a positive integer, and d₁, d₂, . . . , d_n are positive integers such that

d₁ + d₂ + · · · + d_n = 2(n - 1),

then there exists a tree T with V (T) = {v₁, v₂, . . . , v_n} and deg(v_i) = d_i for all i.

5. (a) Let T be a tree on n vertices. Determine P_T(k) in terms of n and k.

(b) For any positive integer n ≥ 3, let C_n be a cycle on n vertices. Let W_n be the graph obtained by adding a new vertex to C_n that is adjacent to every vertex in C_n. Determine P_{W_n}(k) in terms of n and k. Use this to find χ(W_n).