Solve the following:
1. Suppose G is a graph and δ(G) ≥ n/3. Prove that G has one or two connected components.
2. a. Prove if n is odd, then there is no 3-regular graph with n vertices.
b. Give an example of a 3-regular graph with 8 vertices.
c. Prove: For every even n ≥ 4, there is a 3-regular graph with n vertices.
3. Prove: given a graph G with 14 vertices, there is clique in G of size ≥ 3 ( α(G) ≥ 3) or there is an independent set in G of size ≥ 5 (α(G) ≥ 5).
Using notation from class, I'm asking you to give one half of the proof that r (3,5) = 14.
You may use the fact that r(3,4) = 9.
Hint: Consider 2 cases- either there is vertex of degree≥ 5 or every vertex has degree ≤ 4.
4. Suppose T is a tree with n vertices, an every vertex has degree 4 or is a leaf. How many leaves does T have?