Reference no: EM131085073

Assignment 6-

1. Determine the number of ways to color the faces of the following solid figure, where two colorings are equivalent if one can be obtained by another by a symmetry of the figure. Faces can be colored red, white or blue.

2. Consider the graph G whose vertices are the 4-element subsets of the set {1, 2, 3, . . . , 10}, with two vertices adjacent if and only if their intersection is empty.

(a) Show that G is regular.

(b) How many edges does G have?

3. (a) Let G be a bipartite graph on 30 vertices. What is the maximize possible value of |E(G)|?

(b) Let G be a regular bipartite graph whose partition is (A, B). Show that |A| = |B|.

4. Let G be a graph and suppose every vertex in G has degree at least k, where k ≥ 2.

(a) Show that G contains a path with at least k edges in it.

(b) Show that G contains a cycle with at least k + 1 edges in it.

5. Suppose G is a graph on n vertices, and G does not contain a 4-cycle in it. By considering the set of pairs of vertices a particular vertex is adjacent to, prove that

Use this to prove there is a constant C > 0 such that for any graph G on n ≥ 4 vertices that contains no 4-cycle in it, |E(G)| ≤ C · n√n.

You may use, without proof, that if a₁, a₂, . . . , a_n and b₁, b₂, . . . , b_n are sequences of nonnegative numbers, then

(a₁b₁ + · · · + a_nb_n)² ≤ (a₁² + · · · + a_n²)(b₁² + · · · + b_n²).