CPTS553 Graph Theory Assignment 4

Description

1. For the cube graph 𝑄𝑛, the distance 𝐷(𝐚, 𝐛) between two vertices
𝐚 = (𝑎1
, 𝑎2
, … , 𝑎𝑛
) and 𝐛 = (𝑏1
, 𝑏2
, … , 𝑏𝑛
)
is called the “Hamming distance.” This is the number of positions
where 𝐚 and 𝐛 differ. For instance, the Hamming distance between
(0,0,1,0) and (1,1,0,0) is 3 because these two vertices differ in three
positions. In each of the parts A,B below, 𝐷(𝐱, 𝐲) is the Hamming
distance in 𝑄𝑛:
A. Show that if 𝐷(𝐚, 𝐛) and 𝐷(𝐛, 𝐜) have the same parity (i.e., are
both even or are both odd), then 𝐷(𝐚, 𝐜) must be even.
B. Show that if 𝐷(𝐚, 𝐛) and 𝐷(𝐛, 𝐜) have different parity, then 𝐷(𝐚, 𝐜)
must be odd.
2. Consider 𝐾4 as drawn and labeled below:
Since this graph is simple, we can specify a walk by listing only the
vertices. For instance, 𝐶: 1,2,3,4,1 is a 4-cycle; this can be abbreviated
as “12341”. List all of the cycles (abbreviated style is fine) that start
and end at vertex 1 in this drawing of 𝐾4
.
3. For 1 ≤ 𝑚 ≤ 11, let 𝐺𝑚 be the graph with vertex set
𝑉 = {0,1,2,3,4,5,6,7,8,9,10,11}
and where vertices 𝑢 and 𝑤 are adjacent iff 𝑤 − 𝑢 = 𝑚 modulo 12 or
𝑢 − 𝑤 = 𝑚 modulo 12. We observe that 𝐺1 = 𝐶12, a twelve-cycle.
A. For what values of 𝑚 is 𝐺𝑚 connected?
B. What are the possible numbers of components of 𝐺𝑚?
4. Let 𝐺 be a graph and let 𝑒1 and 𝑒2 be edges. Show that if deleting 𝑒1
and 𝑒2 disconnects vertices 𝑢 and 𝑣, then any cycle containing both 𝑢
and 𝑣 must contain both 𝑒1 and 𝑒2
. One approach: You could apply to
the graphs 𝐺 − 𝑒1 and 𝐺 − 𝑒2
the fact that if 𝑒 is a bridge whose
removal disconnects 𝑢 and 𝑣, then any path connecting 𝑢 and 𝑣 must
contain 𝑒.