Please help with the problem below. Define the graph Qn to be the graph whose ve
ID: 1944633 • Letter: P
Question
Please help with the problem below.
Define the graph Qn to be the graph whose vertices are all the binary strings of length n and vertices are adjacent if and only if they differ in exactly one bit. The vertices could be thought of as vectors v = (v1, v2, ... , vn), where v1 {0, 1}; then then uv E(Qn) if and only if vi u, for exactly one , Please prove the following about Qn. |V(Qn)| = 2n. Qn is an n-regular graph; that is. deg(v) = n for each v (Qn). Qn is bipartite; that is, V(Qn) consists of two sets, say X and Y such that X Y = Phi and the only edges of Qn hare one end-vertex in X and the other in Y (so X and Y induce graphs with do edges) Qn it Hamiltonian foe n ge 2.Explanation / Answer
1. The number of vertices of this graph is precisely the number of binary strings of length n, and there are clearly 2n binary strings of length n.
2. Suppose v=(v1,v2,...,vn) is a vertex of the graph. The neighbors of v are precisely those binary strings that differ from v in exactly 1 bit. In other words, if we consider arithmetic modulo 2, then the neighbors of v are precisely the vertices
(v1+1,v2,..,vn), (v1,v2+1,...,vn),...,(v1,v2,....,vn-1,vn+1) and this counts exactly n neighbors. Since v was arbitrary, it follows that every vertex of G has degree n.
3. Consider the following partition: Q1 ={v=(v1,v2,...,vn)| v1+v2+...+vn is odd}, and Q0={v=(v1,v2,...,vn)| v1+v2+...+vn is even}. This clearly is a partition of the vertex set of Q. We claim that there are no edges of the graph inside either of these sets, i.e., for no two v, w in Q0(resp. Q1) are the vertices adjacent. We will show it for Q0; the argument for Q1 is similar.
If v, w are in Q0 then note that the sum of their coordinates is even. If they are adjacent, then since they disagree in exactly one coordinate the sum of the coordinates of w must be exactly one more than the sum of the coordinate for v (or vice-versa) but this contradicts that both these sums are even.
4.This can be proved by induction. It is easy to see that this holds in the case n = 2. Suppose we have proven teh statement for n. Consider Qn+1. Note that the vertices of Qn+1 can be written as (v,0) or (v,1) for some vertex v in Qn.Let us denote the set of vertices of the form (v,0) in Qn+1 by Q' and the set of vertices of the form (v,1) by Q''. It is straightforward to check that the vertices of Q' (resp. Q'') induce a subgraph isomorphic to Qn. By induction there is a Hamiltonian circuit C in Q'. Note that if C =(v,x,y,....z,v) then C' = (v',x',y',...z',v') is a cycle in Q'' where if v=(v,0) then v' =(v,1) is teh corresponding vertex in Q''.
Then consider the following sequence: (v,x,y,..,z,z',....y',x',v',v). This is clearly a cycle in Q and it is clear that all the vertices of Qn+1 are in this cycle, so this proves that Qn+1 is hamiltonian. The completes the induction.