Assignment 1-
1. For a pair of vertices u, v in a graph G, the distance between u and v, denoted d(u, v), is the number of edges in the path from u to v using as few edges as possible. The diameter of G is
maxu,v∈V (G)d(u, v).
Let d, k be positive integers. Let G be a graph with maximum degree d and diameter k. Show that
|V (G)| ≤ 1 + di=0∑k-1(d - 1)i.
Give an example of an G with (d, k) = (3, 2) where equality holds.
2. A cycle in a graph is Hamiltonian if it goes through all vertices. Suppose G is a graph on n vertices with the property that for every pair of vertices u, v that are not adjacent, deg(u) + deg(v) ≥ n. Prove that G has a Hamiltonian cycle. Can we replace n in the previous inequality by any value smaller than n and guarantee G is Hamiltonian?
3. Determine, with proof, the value of ex(n, K1,r) for every pair of positive integers n, r.
4. (a) Suppose G is a graph not containing C4 (a cycle on four vertices) as a subgraph. Prove that
![2125_Figure.png](https://secure.tutorsglobe.com/CMSImages/2125_Figure.png)
and use this to prove there is a constant C > 0 such that
ex(n, C4) ≤ C · n√n, for all n ≥ 4.
(b) Let q be any prime and Fq be the finite field of order q. Consider the bipartite graph Gq with bipartition (Pq, Vq) where Pq is the set of 2-dimensional subspaces of Fq3 and Vq is the set of 1-dimensional subspaces of Fq3, with p ∈ Pq adjacent to v ∈ Vq if and only if v lies in p. Show that for any prime q, Gq does not contain C4 as a subgraph, and
|E(Gq)| ≥ n√n/2√2,
where n = |V (Gq)|. Hence there is a constant C > 0 such that for infinitely many n,
ex(n, C4) ≥ C · n√n.
Recall that for any graphs G1, G2, . . . , Gk, we define R(G1, G2, . . . , Gk) to be the smallest positive integer n so that for any k-coloring of the edges of Kn, say with colors c1, c2, . . . , ck, there must exist some i for which Gi is a subgraph, all of whose edges are colored with color ci. For simplicity, we denote R(Kr1, Kr2, . . . , Krk) by R(r1, r2, . . . , rk).
5. Let m, n be positive integers, and assume (m - 1)|(n - 1). Determine, with justification, a function f(m, n) for which R(T, K1,n) = f(m, n) for every tree T on m vertices.
6. In this problem, we shall prove R(3, 4) = 9.
(a) Consider the graph G whose vertex set is {1, 2, 3, 4, 5, 6, 7, 8}, with i and j adjacent if and only if i - j = ±1 or ±4 mod 8. Show that G does not have K3 and a subgraph, and G does not contain K4 as a subgraph.
(b) Show that for any graph G on 9 vertices, either G has K3 as a subgraph, or G has K4 as a subgraph. (Hint: Consider three cases: The existence of a vertex with degree at least 4, the existence of a vertex of degree at most 2, and G being 3-regular).
7. (a) Show that ![811_Figure1.png](https://secure.tutorsglobe.com/CMSImages/811_Figure1.png)
(b) Suppose the integers {1, 2, . . . , n} are partitioned into r disjoint sets A1, A2, . . . , Ar. Show that if n ≥ ⌊e · r!⌋ + 1, then one of the sets Ai contains three elements x, y, z such that x + y = z.