N cube Graph

Question

In N-cube graph we have no. of vertices = $2^N$ and no. of edges =  $N*2^{N-1}$
Can anyone explain how we get this no. of edges?

Answer 1

Check here for 1-cube graph we have no. of vertices =2 and  no. of edges = 1

                  2 -cube graph we have no. of vertices =4         and   no. of edges = 4

                   3-cube graph we have no. of vertices =8          and  no. of edges = 12

∗2N−1

Answer 2

Hi , 

I would like to explain the above question :)

Look For a N Cube graph   : This graph has got its name as "N "cube because here each vertex is represented By N bits . 

Say for 1 cube graph : we would have vertex represented by 1 bit . so number of vertex possible with 1 bit is 0/1 ( 2 vertex==2ⁿ  where n is 1)

Similarly take for 2 cube graph : here each vertex would be represented by 2 bits . so number of vertex possible is 00,01,10,11

So there are 4 vertex possible ( 4=2² where n is 2)

Hence in this way we can generalize that For N cube graph we can have vertex which is represent which is rep By N bit and number of vertex possible is 2^N 

And now let us see How to find the no of edges :

( If you seen the dig given below ) A vertex is joined by another vertex if its both vertex bits representation differ by atmost 1 bit .

say if A has 001 and B has 101 we can join AB but if C has 110 so here we cant join neither AC Or BC. 

So if a vertex is rep by N bit then it can be associated with other (n-1) vertex with change in any of these N bit at distance of 1 ( Only 1 bit to differ in any vertex ) . However this condition should be maintained if we are joining vertex .

Hence no of edges =  N * 2^{N-1  (}where first N mean change in any of N bit and 2^n-1 mean it can/cant  be associated with neighbouring vertex with the above condition specified ) 

Answer 3

Lets take n=3, no of vertex possible = $2^3$=8. We can name the vertex as 000, 001,010........111.

We can calculate No of edges possible from  1st vertex 000 ,by fixing any 2 bits and changing 1 bit as shown below:

000->001

000->010

000->100

So total egdes possible from 000 is 3(i.e = n)

Similarly from  every other vertex 3 edges is possible. So total $2^3$ * 3=24 (i.e $2^n$ * n)edges. However each edge is counted twice(e.g vertex 0 has edges to vertices 1, 2 &4 which will again be counted while calculating number of edges from vertices 1,2 &4 resp).

Therefore total number of edges for n bits will be ($2^n$ * n)/2=$2^n$$^-$$^1$ * n

Comments

Best Answer 🏆