graph theory!!! what is dis!!!!!?

4. Let n and k be integers satisfying 2 <= k<=  n. The graph G(n; k) is

de ned as follows: its vertex set is the set of all binary strings of length

n that have exactly k 1's. Two strings are joined by an edge in G(n; k)

precisely when they di er in exactly two positions.

(a) Draw G(6; 2).

(b) Determine the numbers of vertices and edges in G(n; k).

(c) Show that G(n; k) is connected.

1 Answer

Relevance
  • 10 years ago
    Favorite Answer

    a) There are 6 choose 2 = 15 vertices in G(6;2), because a vertex is determined by choosing the two positions (of the six) in which to place 1s. A given vertex, say 110000, has 2*4 =8 neighbors, because in order to get a neighbor you take a 1 and a 0 and switch them, so that 011000 is a neighbor of 110000.

    Drawing this is kind of a pain and this isn't art school

    b) The number of vertices is n choose k, and the number of neighbors in a given vertex v in G(n;k) is (k)(n-k). For in order to differ from v in two spots, one of the spots must be a 1 where v has a 0 and the other spot must be a 0 where v has a 1. Thus if you count pairs (v,e) where v is a vertex and e is an edge containing v, you get (n choose k)(k)(n-k). But this double counts the edges because you count each vertex on an edge, so that the true number of edges is (n choose k)(k)(n-k)/2.

    c) Note that if k=n then the proposition is trivial because there is only one vertex. Thus assume that k<n.

    Let v and v' be vertices of G(n;k) and let d(v,v') denote the Hamming distance between v and v', i.e. the number of places in which v and v' differ. We show that for any d(v,v') the vertices v and v' are connected by a path in G(n;k). If d(v,v')=2 then the vertices v and v' differ only in two places, and this is precisely the condition that v and v' be joined by an edge. Assume that if d(w,w') < k, then w and w' are joined by an edge, and assume that d(v,v')=k. Suppose that v differs from v' in 1=spot i and 0=spot j, which must exist because the vertices v and v' are distinct and they can't differ just in the 0s or just in the 1s.

    Let v'' be the result of changing v in spot i to 0 and spot j to 1. Then v and v'' are connected by an edge, because they differ only in one spot, and the distance from v'' to v' is strictly less than k, so that v'' and v' are connected. Thus v is connected to v'' and v'' is connected to v', so that v is connected to v'. Thus if d(v,v')=k, the vertices v and v' are connected in G(n;k). Thus by induction G(n;k) is connected.

Still have questions? Get your answers by asking now.