- 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 𝑄𝑛:
- Show that if 𝐷(𝐚, 𝐛) and 𝐷(𝐛, 𝐜) have the same parity (i.e., are both even or are both odd), then 𝐷(𝐚, 𝐜) must be even.
- Show that if 𝐷(𝐚, 𝐛) and 𝐷(𝐛, 𝐜) have different parity, then 𝐷(𝐚, 𝐜) must be odd.
- 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.
- 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?
- What are the possible numbers of components of 𝐺𝑚?
- 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 𝑒.
