Reference no: EM133074929

Problem 1.

a) For simple graph G, how does X (G) relate to independent sets in G.

b) Prove that the complete graph K_n has a decomposition consisting of two copies of a some graph H if and only if n or n - 1 is a multiple of 4.

Problem 2.

Prove that if K_n decomposes into triangles, then n- 1 or n-3 is a multiple of 6.

Problem 3.
What is the maximum possible degree in a SIMPLE undirected graph on n vertices? What is the minimum possible degree?

Problem 4.
What is the minimum size of the automorphism group of a simple directed graph having more then five vertices. Describe explicitly such a graph.

Problem 5.

Give a detail description for a construction of an infinite s equence of graphs G₁, G₂, .... subject to the following constraints

|V (G_k)| = 1 + 3 . (2^k-1 - 1) + 3.4.2^k-1,

vertices for each positive integer k > 0. None the graphs from the sequence has a cycle of length 5. In addition, every vertex in each graph from the sequence has degree either 3 or 4. Finally, positive integer k > 0

G_k has (3!).3.2(k-1) cycles of length 4,
G_k has 3.2(k-1)(4/3) cycles of length 3,

and not other cycles. Explain in words why your construction satisfies all the requirements above.