*** Please inform if something is not defined properly or unclear or miss-tagged. Also if you vote up/down it would be helpfull if you leave a comment.***

Introduction: Given a matrix A of a $k$ regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $A_x$ is the symmetric matrix of the graph $(G-x)$, where $C$ is the symmetric matrix of the graph created by vertices of $(G-x)$ which are adjacent to $x$ and $D$ is the symmetric matrix of the graph created by vertices of $(G-x)$ which are not adjacent to $x$.

$$ A_x = \left( \begin{array}{ccc} C & E & 0 \\ E^{T} & D & 1\\ 0 & 1 & 0\\ \end{array} \right) $$

It should be noted that

1. Interchanging/swapping any two rows (or columns) of $C$ does not affect matrix $D$ (and vice versa).

2. Any change in $C$ or $D$ or both $C$ and $D$ changes matrix $E$.

If some vertices of $G$ is rearranged (i.e., permuted), $A$ will be different, say, this new matrix is $B$. Again, matrix $B$ can be divided into 4 sub matrices based on adjacency of vertex $x \in G$ and $ B_x$ can be obtained. $ B_x= \left( \begin{array}{cc} S & R \\ R^{T} & Q\\ \end{array} \right) $
Given: Both matrices $A,B$ are divided based on same vertex $x$, and $E,R$ are zero matrices or matrices of all 1's. In order to get $A_x=B_x $, it must be shown , that, $D=Q$ and $S=C$ (so that $A_x=B_x $ happen).
Claim: ***To get $A=B$, reordering of $Q,S$(so that $A_x=B_x $ happens) can be done independently i.e. the total complexity of reordering$B_x$=complexity of reordering$S$+ complexity of reordering$Q$(both are independently added to the total complexity, not multiplied. ) ***