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 both even or are both odd), then ( ,
B. Show that if ( , ) and ( , ) have must be odd.
2. Consider 4 as drawn and labeled below:
the same parity (i.e., are
) must be even.
different parity, then ( , )
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 .
