1,192 views

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

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

edited

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.

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.

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

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.

by

1 vote
1
522 views