title: Algorithm for determining if 2 graphs are isomorphic
body: <p>Disclaimer: I'm a total newbie at graph theory and I'm not sure if this belongs on SO, Math SE, etc.</p>
  
  <p>Given 2 adjacency matrices A and B, how can I determine if A and B are isomorphic.</p>
  
  <p>For example, A and B which are not isomorphic and C and D which are isomorphic.</p>
  
  <pre><code>A = [ 0 1 0 0 1 1     B = [ 0 1 1 0 0 0
        1 0 1 0 0 1           1 0 1 1 0 0
        0 1 0 1 0 0           1 1 0 1 1 0
        0 0 1 0 1 0           0 1 1 0 0 1
        1 0 0 1 0 1           0 0 1 0 0 1
        1 1 0 0 1 0 ]         0 0 0 1 1 0 ]
  
  C = [ 0 1 0 1 0 1     D = [ 0 1 0 1 1 0
        1 0 1 0 0 1           1 0 1 0 1 0
        0 1 0 1 1 0           0 1 0 1 0 1
        1 0 1 0 1 0           1 0 1 0 0 1
        0 0 1 1 0 1           1 1 0 0 0 1
        1 1 0 0 1 0 ]         0 0 1 1 1 0 ]   
  
  (sorry for this ugly notation, I'm not quite sure how to draw matrices on SO)
  </code></pre>
  
  <p>Here's how I've started my algorithm (pardon my lack of mathematical rigor) please help me complete/correct!</p>
  
  <ol>
  <li>If size (number of edges, in this case amount of 1s) of A != size of B => graphs are not isomorphic</li>
  <li>For each vertex of A, count its degree and look for a matching vertex in B which has the same degree <em>and</em> was not matched earlier. If there is no match => graphs are not isomorphic.</li>
  <li>Now that we cannot quickly prove that A and B are not isomorphic, what's the next step?
  Would it be correct try every permutation of lines in A until A matches B? Really not sure about this one...</li>
  </ol>