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