%The graph from kalamazoo 2000 - adjacency matrix
% Label vertices 1234 for inner 4-cycle, 
%then clockwise 567 for first outer 5-cycle, 9 10 11 for the next etc.
% The adjacency matrix is 16 by 16. Here we go!
% I have typed the rows and columns in groups of four - three-three-three-three.
K = [  0   1   0   1    1   0   0    0   0   0    0   0   0    0   0   1;
          1   0   1   0    0   0   1    1   0   0    0   0   0    0   0   0;
          0   1   0   1    0   0   0    0   0   1    1   0   0    0   0   0;
          1   0   1   0    0   0   0    0   0   0    0   0   1    1   0   0;
 
          1   0   0   0    0   1   0    0   0   0    0   0   0    0   0   0;
          0   0   0   0    1   0   1    0   0   0    0   0   0    0   0   0;
          0   1   0   0    0   1   0    0   0   0    0   0   0    0   0   0;
 
          0   1   0   0    0   0   0    0   1   0    0   0   0    0   0   0
          0   0   0   0    0   0   0    1   0   1    0   0   0    0   0   0
          0   0   1   0    0   0   0    0   1   0    0   0   0    0   0   0
 
          0   0   1   0    0   0   0    0   0   0    0   1   0    0   0   0
          0   0   0   0    0   0   0    0   0   0    1   0   1    0   0   0
          0   0   0   1    0   0   0    0   0   0    0   1   0    0   0   0
 
          0   0   0   1    0   0   0    0   0   0    0   0   0    0   1   0
          0   0   0   0    0   0   0    0   0   0    0   0   0    1   0   1
          1   0   0   0    0   0   0    0   0   0    0   0   0    0   1   0];

%Calculate number of spanning trees using method given by Matrix Tree Theorem         
Q= - K;
for i=1:16, Q(i,i)=degree(16,i,K); end;
%this is the matrix Q specified by the matrix tree theorem
disp('the number of spanning trees of the Kalamazoo graph is ...');
Qstar=Q(2:16,2:16); 
%this means Qstar is the matrix obtained by deleting row 1, col 1 of Q
%so that is the matrix of which we have to calculate the determinant.
det(Qstar)