Graph Theory
Assignment 1
1. Sketch the following graphs described as sets of vertices and adjacency rules (“iff” means “if and
only if”). Also, give the values of 𝑛 and 𝑚 for each graph.
A. 𝑉 = {(𝑖,𝑗): 1 ≤ 𝑖,𝑗 ≤ 3}
And (𝑖,𝑗) is adjacent to (𝑝, 𝑞) iff |𝑝 − 𝑖| + |𝑞 − 𝑗| = 1
B. 𝑉 = {0,1,2,3,4,5,6,7}
And 𝑖 is adjacent to 𝑗 iff 𝑖 − 𝑗 is odd.
C. 𝑉 = {(0,0,1), (0,0, −1), (0,1,0), (0, −1,0), (1,0,0), (−1,0,0)}
And (𝑖,𝑗, 𝑘) is adjacent to (𝑝, 𝑞, 𝑟) iff they disagree in two positions.
D. 𝑉 = {(0, ±1, ±2), (±1, ±2,0), (±2,0, ±1)} . Here, the ± symbols are completely independent,
so (0, ±1, ±2) represents (0,1,2), (0,1, −2), (0, −1,2), and (0, −1, −2).
And (𝑖,𝑗, 𝑘) is adjacent to (𝑝, 𝑞, 𝑟) iff the Euclidean distance 𝑑 between them satisfies 0 < 𝑑 < 3.
2. Give a “set of vertices and rule(s) for edges” recipe for the following two graphs:
A. B.
