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.

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

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