We found, implemented and tested algorithm
for graph isomorphism and it appears to be polynomial
time if the graph is rigid.

>Q1 Is the algorithm below correct and polynomial time for rigid graphs?


A graph is rigid if its automorphism group is trivial.

Two graphs $G_1,G_2$ of order $n$ are isomorphic iff there exist permutation
matrix $P$ such that $P A_1 P^{-1}=P A_1 P^T = A_2$ where $A_1,A_2$ are their
adjacency matrices. We believe it is rigorous to multiply by $P$
and have $P A_1 = A_2 P$.

Let $P$ be $n$ by $n$ matrix with entries $n^2$ variables $x_{i,j}$.

Construct the following system of linear equations $J$.

For the rows $k$ of $P$ add the equations $\sum_{1 \le i \le n} x_{k,i} = 1$. 
For the columns $k$ of $P$ add the equations $\sum_{1 \le i \le n} x_{i,k} = 1$. 

This is necessary condition $P$ to be permutation and if the variables are zero or one it is
sufficient.

Let $M = P A_1 - A_2 P$. The entries of $M$ are linear equations
in $x_{i,j}$.

For all $n^2$ entries of $M$ add to $J$ the constraints $M_{i,j}=0$.

$J$ has $n^2+2n$ linear equations in $n^2$ variables.

If we can find zero/one solution to $J$, we can solve GI.

Main idea for finding the unique zero/one solution.

Guess variable $x_{i,j}=1$. This forces all $x_{i,k}=0$ for the row
and $x_{k,j}=0$ for the columns. These are $2n$ equations in $2n-1$
variables. Add these equation to $J$ and let the resulting system
be $J'$. Experimentally, if we make the wrong guess in the unique solution,
$J'$ doesn't have any solutions over the rationals and this can be found using linear algebra.
If the guess is wrong, set $x_{i,j}=0$ and substitute in $J$.
If the guess is correct, we might find zero/one solution over the rationals.

Repeat for all $n^2$ variables.

**ADDED** explaining the "guessing" part.
$J$ has infinitely many integer solutions but single zero/one solution
since the graph is rigid. Let $P'$ be the matrix of the unique zero/one solution. We are guessing $P'$ entry by entry. Assume $P'_{1,1}=1$.
In $J'$ add $x_{1,1}=1,x_{1,i}=0,x_{i,1}=0,1 \le i \le n$. This reduces the number
of variables by $2n-1$. Since the guess is correct, we keep the unique
zero/one solution and $J'$ has integer solution. In practice the integer
solution is zero/one over the integers.

Assume we make the wrong guess $P'_{1,2}=1$. Add the rows and columns
constraints $x_{1,2}=1,x_{1,i}=0,x_{i,2}=0,1 \le i \le n$. Experimentally in the wrong guess
$J'$ doesn't have any solutions over the integers and hence no zero/one
solution. In $J$ replace $x_{1,2}=0$ in all equations, decreasing the
variables by $1$


The complexity of the algorithm is polynomial in $n$, probably something
like $O(n^8)$.

Our main pain is that guessing the wrong solution might not be detected
over the rationals or integers.