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.
