edited by
1,446 views
11 votes
11 votes

For a positive integer $n$, let $G = (V, E)$ be a graph, where $V = \text{{0,1}}^n$, i.e., $V$ is the set of vertices has one to one correspondence with the set of all $n$-bit binary strings and $E = \{(u,v) \mid u, v$ belongs to $V, u$ and $v$ differ in exactly one bit position$\}$.

  1. Determine size of $E$
  2. Show that $G$ is connected
edited by

2 Answers

Best answer
14 votes
14 votes

These types of graphs are also known as hypercube graphs.

  1. Consider any vertex $v$. Exactly $n$ vertices have a hamming distance of $1$ from $v$. (Reason: Consider the vertex which is exactly the same bit pattern as $v$ except the first bit as $v_1$.  $v_2$ differs from $v$ in only the 2nd bit and so on till $v_n$ which is different from $v$ in last bit).
    Now there are total of $2^n$ vertices (Since each vertex corresponds to a bit string and for n bits there are $2^n$ bit strings.).
    Consider the basic theorem for undirected graphs which says that sum of degrees of vertices is equal to twice the no. of edges.
    Using that here we get:
    $2^n*n = 2*e$ where $e$ is the no. of edges.
    Thus no. of edges = $2^{n-1}n$
     
  2. A graph is called connected if there's a path between any two vertices.
    Consider any vertices $v_x$ and $v_y$. Suppose hamming distance between them is $k$. Consider the first different bit $k_1$. You simply reach $v_{k1}$ from $v_x$  which differs from $v_x$ only in that bit. Now $v_{k1}$ and $v_y$ differ from each other by $k-1$ bits. You continue to do this until you reach $v_y$. Thus any two vertices are connected by a path of $k$ where $k$ is the hamming distance between them.
edited by
1 votes
1 votes

Lets keep it simple.

1. 

Its a hypercube graph so edge count is : 

$n*2^{n-1}$ ...... [ or $n*\frac{2^n}{2}$ using handshaking lemma ] 

 

2. 

Using above solution : 

For any graph to be connected on $n$ vertices edges must be at least $n-1$. 

and term $2^{n-1}$ cant be zero so atlest edges will be $n$ wich shows graph is connected.

 

Related questions

1 votes
1 votes
1 answer
1
akash.dinkar12 asked Apr 8, 2019
846 views
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.
13 votes
13 votes
2 answers
2
neha.i asked May 11, 2017
2,737 views
Suppose $X$ is distributed as Poisson with mean $λ.$ Then $E(1/(X + 1))$ is$\frac{e^{\lambda }-1}{\lambda }$$\frac{e^{\lambda }-1}{\lambda +1}$$\frac{1-e^{-\lambda }}{\l...
12 votes
12 votes
1 answer
3
Devasish Ghosh asked Mar 9, 2017
1,347 views
Design a context free grammar for the language consisting of all strings over $\mathbf{\{a,b\}}$ that are not the form $\mathbf{ww}$ for any string $\mathbf{w}$