in Graph Theory edited by
1,192 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
in Graph Theory edited by
1.2k views

2 Answers

14 votes
14 votes
Best answer

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
by

3 Comments

edited by

For proving that graph is connected we can also use this theorem 

Let G be an n-vertex graph. If every vertex has a degree of at least (n-1) / 2 then G is connected.

Proof: https://books.google.co.in/books?id=g6X2VWuB8qIC&lpg=PP1&pg=PA38#v=onepage&q&f=false 

PS: But here we have $2^n$ vertices and Each one has degree n. So here the above theorem is not applicable. To be applicable each vertex should have degree at least ($2^n$ - 1) / 2.

8
8
All such graph will have a structure similar to that of a boolean algebra?
0
0
nice explanation @kal
0
0
1 vote
1 vote

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