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 π.
