Let condition 1 = $[(u_{0} \neq v_{0})\wedge (u_{n-1}\doteq v_{n-1})]$ ($1^{st}\textrm{ bit different and last bit same}$)
and condition 2 =$ [(u_{0}=v_{0})∧(u_{n-1}≠v_{n-1})] $ ($1^{st}\textrm{ bit same and last bit different}$)
Connected Components
$\rightarrow$ We can make the vertices adjacent if either condition 1 or condition 2 satisfies.
$\rightarrow$ $u_{0}$ bits of first half nodes will be $0$ so we can connect them in serial order and $u_{0}$ bits of other half will be $1$ so we can connect them in serial order using condition 2
$\rightarrow$ Then we can connect $1^{st}$ half with other half by connecting $1^{st}$ node of first half with $1^{st}$ node of other half
$\rightarrow$ So connected components will always be $1$ (except for n=1)
$\rightarrow$ Now we need to find degree of node.
$\rightarrow$ Lets take $n=2$
$\rightarrow$ We have $2^{2}$ vertices.
$\rightarrow$ The vertices are $A(0,0),B(0,1),C(1,0),D(1,1)$
Vertices |
$u_{0}$ |
$u_{1}$ |
$A(a_{0}$) |
0 |
0 |
$B(a_{1}$) |
0 |
1 |
$C(a_{2}$) |
1 |
0 |
$D(a_{3}$) |
1 |
1 |
Here,
$\rightarrow$ we can connect A with B and C with D based on condition 2.
$\rightarrow$ we can connect D with B and C with A based on condition 1.
$\rightarrow$ No more connections(edges) are possible.
NOTE :- here $\rightarrow$ are bi-directional edges.
$\therefore$ We have $1$ connected component and degree of each node is $2^{1}$=${2}$ for $n=2$
Lets take $n=3$
We have $2^{3}$ vertices.
The vertices are $A(0,0,0),B(0,0,1),C(0,1,0),D(0,1,1),E(1,0,0),F(1,0,1),G(1,1,0),H(1,1,1)$
Vertices |
$u_{0}$ |
$u_{1}$ |
$u_{2}$ |
$A(a_{0})$ |
0 |
0 |
0 |
$B(a_{1})$ |
0 |
0 |
1 |
$C(a_{2})$ |
0 |
1 |
0 |
$D(a_{3})$ |
0 |
1 |
1 |
$E(a_{5})$ |
1 |
0 |
0 |
$F(a_{6})$ |
1 |
0 |
1 |
$G(a_{7})$ |
1 |
1 |
0 |
$H(a_{8})$ |
1 |
1 |
1 |
Here we need to Focus on $u_{0}$ and $u_{2}$ only.
$\rightarrow$ we can connect A with B ,A with G, B with C,B with F, C with D , C with E,D with A , D with H ,E with F, F with G , G with H ,H with B and H with E based on condition 2.
$\rightarrow$ we can connect E with A, F with B , G with C and F with D based on condition 1.
$\rightarrow$ No more connections(edges) are possible.
NOTE :- here $\rightarrow$ are bi-directional edges.
$\therefore$ We have $1$ connected component and degree of each node is $2^{2}$=$4$ for $n=3$
So in general we can see that for $n>=2$ nodes we always have $1$ connecetd component and degree of each node is $2^{n-1}$.
$\Rightarrow$ For $n =8$ we will have $1$ connected component and degree of each node will be $2^{8-1}$=$128$
so $x = 128$ and $y=1$
$x+10y = 128 + 10 = 138$