Graph Theory
Assignment 2
1. Consider simple bipartite graphs (i.e., no loops or parallel edges) with 𝑛 = 200. What are bounds
on the possible values of 𝑚 for such a graph? It’s enough to provide a tight lower bound and a tight
upper bound. Here, the word “tight” means that an example of a graph with that number of edges
exists.
2. Let 𝑝 and 𝑞 be positive integers with 𝑝 < 𝑞. Find tight lower and upper bounds on the length of a
path in 𝐾𝑝,𝑞, the complete bipartite graph on 𝑝 and 𝑞 vertices. Recall that the length of a path is the
number of edges in the path.
3. Let ℤ10 = {0,1,2,3,4,5,6,7,8,9} with arithmetic modulo 10. For 𝑘 ∈ ℤ10, let 𝐺𝑘 be the graph where
𝑉 = ℤ10 and vertices 𝑖 and 𝑗 are joined by an edge if and only if 𝑖 and 𝑗 differ by 𝑘 mod 10. As
examples, 𝐺1 is the cycle graph 𝐶10 and 𝐺3 is sketched in figure 1 below. For which values of 𝑘 is 𝐺𝑘
connected?
Figure 1. A sketch of 𝐺3
4. Recall that a graph 𝐺 is “cubic” if and only if it is 3-regular (i.e., every vertex has degree 3.)
A. Show that there exists no cubic graph with an odd number of vertices.
B. Show that there exists a simple cubic graph with 4 vertices.
C. For every integer 𝑛 ≥ 3, show how to construct a simple cubic graph with 2𝑛 vertices. You
can do this using a sketch of small examples with an obvious generalization, or by specifying
a set 𝑉 with 2𝑛 elements and a recipe for joining them that produces the desired graph.
