*I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in my approach, I will not use matrix and recursive process, instead, this time I describe the problem for first two consecutive steps. Despite my effort, if it is not clear, please, let me know.*


**Problem Description:**
 $G$ is a $r$ regular graph. $G$ is $k$ connected( not a complete or cycle graph). A vertex of $G$ is $x\_1$. 
All vertices which are not adjacent to $x\_1$ create a sub-graph $C\_1$.
 All vertices adjacent to $x\_1$ create a sub-graph $, D\_1 $. 
 These $C\_1, D\_1 $ are $s\_1 , t\_1 $ regular graphs respectively (given condition) .
A vertex of $D\_1$ is $x\_2$. 


Using same method, based on adjacency of $x\_2$ , $D\_1$ can be divided. 


All vertices which are not adjacent to $x\_2$ create a sub-graph $C\_2$. 
 All vertices adjacent to $x\_2$ create a sub-graph $, D\_2 $. 
 These $C\_2, D\_2 $ are $s\_2 , t\_2 $ regular graphs respectively(given condition).


**Question**: According to above given conditions/situation/context, is it possible to have no edge between graph $C\_2$ and $ D\_2 $?


**Motivation:** I am studying graph isomorphism problem. In a certain kind of construction, above described situation arises and increases search cases. I am trying to find out when this (no edge between sub-graphs $C\_y, D\_y$ ) can happen. I hope, this post is an appropriate MO question.



Decomposition of a regular graph and connected subgraphs
Edit: How about this counterexample for the case $s\_2,t\_2>0$:


$G=(V,E)$ with $V=\{x\_1\}\cup\{u\_i^k\ |\ 1\le i\le n,1\le k\le 4\}$, and $E$ being the union of


* $\{(x\_1,u\_i^k)\ |\ 1\le i\le n, k\in\{1,4\}\}$,
* $\{(u\_i^k,u\_j^k)\ |\ 1\le i<j\le n, k\in\{1,4\}\}$,
* $\{(u\_i^k,u\_j^{k+1})\ |\ 1\le i,j\le n, 1\le k\le 3\}$.


$G$ is $2n$-regular. Decomposing with respect to $x\_1$, we get that $C\_1$ is the complete bipartite graph on $\{u\_i^2\ |\ 1\le i\le n\}$ and $\{u\_i^3\ |\ 1\le i\le n\}$ (and thus $n$-regular), while $D\_1$ is the disjoint union of the complete graphs on $\{u\_i^1\ |\ 1\le i\le n\}$ and $\{u\_i^4\ |\ 1\le i\le n\}$
(and thus $(n-1)$-regular).


Picking (for example) $x\_2=u\_1^1$, we now get that $C\_2$ is the complete graph on $\{u\_i^4\ |\ 1\le i\le n\}$, and $D\_2$ is the complete graph on $\{u\_i^1\ |\ 2\le i\le n\}$. There are no edges between these, and they are $(n-1)$- and $(n-2)$-regular, respectively.


Old, simpler answer:


I will assume that you meant $x\_i$ to not be included in $C\_i$ (otherwise you would need to go for an example where $D\_2$ is the null graph).


For $k\in\mathbb{N}$, consider the graph $G = (\{u\_1,\dots,u\_{2k},v\_1,\dots,v\_{2k-1}\},E)$, where $E$ contains the following edges:


* $(u\_{2i-1},u\_{2i})$ for $i=1,\dots,k$;
* $(u\_i,v\_j)$ for all $i,j$.


$G$ is $2k$-regular. Picking $x\_1=v\_1$, $C\_1$ is $(\{v\_i\ |\ i>1\},\emptyset)$ ($0$-regular), and $D\_1$ is $(\{u\_1,\dots,u\_{2n}\},\{(u\_{2i-1},u\_{2i})\ |\ 1\le i\le k\})$ ($1$-regular).


Picking $x\_2=u\_1$, we get $C\_2=(\{u\_i\ |\ i>2\},\{(u\_{2i-1},u\_{2i})\ |\ 1<i\le k\})$ ($1$-regular) and $D\_2=(\{u\_2\},\emptyset)$ ($0$-regular), with no edges between them.


