Graph Theory  Assignment 3

Graph Theory 
Assignment 3
1. Show that these two graphs are isomorphic by finding a bijection 𝜓:{0,1,2,3,4,5,6,7,8,9} →
{𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖,𝑗} that preserves adjacencies.
2. Let 𝑎 and 𝑏 be integers at least 2. Find the maximum value among distances between vertices in
each of the following graphs:
a. 𝑃𝑎
b. 𝐶𝑎
c. 𝐾𝑎
d. 𝐾𝑎,𝑏
e. 𝑄𝑎
3. We investigate using the phrase “distance between vertices” to denote the length of a shortest path
between two vertices in a graph 𝐺. We define 𝑑(𝑢, 𝑣) as the length of a shortest 𝑢, 𝑣-path in 𝐺. If
there is no such path, then we define 𝑑(𝑢, 𝑣) = ∞. Notice that if 𝑑(𝑢, 𝑣) < ∞, then there must be a
𝑢, 𝑣-path in 𝐺.
A. Explain why 0 ≤ 𝑑(𝑢, 𝑣) for all vertices 𝑢 and 𝑣.
B. Under what conditions on 𝑢 and 𝑣 would the equation 𝑑(𝑢, 𝑣) = 0 be true?
C. Explain why 𝑑(𝑢, 𝑣) = 𝑑(𝑣, 𝑢) for all vertices 𝑢 and 𝑣.
D. Suppose 𝑑(𝑢, 𝑣) < ∞ and 𝑑(𝑣, 𝑤) < ∞. Why must 𝑑(𝑢, 𝑤) < ∞ hold? Here, you’ll want to
consider a shortest 𝑢, 𝑣-path 𝑃 and a shortest 𝑣, 𝑤-path 𝑄. What can you do with 𝑃 and 𝑄?
E. Suppose 𝑑(𝑢, 𝑤) = ∞. What can you say about 𝑑(𝑢, 𝑣) or 𝑑(𝑣, 𝑤)?
F. Show that if 𝑑(𝑢, 𝑣) < ∞ and 𝑑(𝑣, 𝑤) < ∞, then 𝑑(𝑢, 𝑤) ≤ 𝑑(𝑢, 𝑣) + 𝑑(𝑣, 𝑤).
G. What can you say about 𝑑(𝑢, 𝑤) if 𝑑(𝑢, 𝑣) < ∞ and 𝑑(𝑣, 𝑤) = ∞?
H. What can you say about 𝑑(𝑢, 𝑤) if 𝑑(𝑢, 𝑣) = ∞ and 𝑑(𝑣, 𝑤) = ∞?
1
3 2
4
0
5
6
8 7
9
a
b c d
e f g h i j
4. We discuss the Cartesian product of two simple graphs in this question; particularly, we avoid
discussing parallel edges here to make things easier. Let 𝐺 = (𝑉𝐺,𝐸𝐺
) and 𝐻 = (𝑉𝐻,𝐸𝐻) be graphs.
Their Cartesian product is the graph 𝐺 × 𝐻 whose vertex set is
𝑉𝐺 × 𝑉𝐻 = {(𝑣, 𝑤): 𝑣 ∈ 𝑉𝐺 and 𝑤 ∈ 𝑉𝐻}
and where vertices (𝑣1, 𝑤1
) and (𝑣2, 𝑤2
) are joined by an edge if and only if one of the following
conditions is met:
a) 𝑣1 = 𝑣2 and 𝑤1𝑤2 ∈ 𝐸𝐻,
b) 𝑣1𝑣2 ∈ 𝐸𝐺 and 𝑤1 = 𝑤2.
As an example, the Cartesian product of 𝑃𝑎 and 𝑃𝑏 is the “grid graph” 𝑃𝑎 × 𝑃𝑏. We show 𝑃4 × 𝑃3
below:
A) In terms of |𝑉𝐺
| and |𝑉𝐻|, what is |𝑉𝐺×𝐻|?
B) In terms of |𝑉𝐺
|,|𝑉𝐻|,|𝐸𝐺
|, and |𝐸𝐻|, what is |𝐸𝐺×𝐻|?
C) Suppose 𝐺 is 𝑎-regular and 𝐻 is 𝑏-regular. Show that 𝐺 × 𝐻 is (𝑎 + 𝑏)-regular.
Figure 1. A sketch of 𝐺3
5. 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.