Graphs, Matrices, Isomorphism

Isomorphism

Two graphs, G=(V,E,I) and H=(W,F,J), are isomorphic (normally written in the form G=H, where the = should have a third wavy line above the the two parallel lines), if there are bijections f:V->W and g:E->F such that eIv if and only if g(e)Jf(v). Two isomorphic graphs must have exactly the same set of parameters. For example, the cardinalities of the vertex sets must be equal, the cardinalities of the edge sets must be equal, the (ordered) degree sequences must be the same, any graph polynomials must agree on the two graphs, etc.

Let G=(V,E,I) be a graph. For the sake of the next definition, give a linear ordering to the set of vertices and a linear ordering to the set of edges. Also, give each edge an orientation - that is for each edge e incident with two vertices v and w, arbitrarily pick p(e)=v and n(e)=w. We define the incidence matrix, M(G), to be the |V| by |E| matrix whose entries are chosen from {0,1,-1} such that the (i,j)-entry is 1 if p(e)=v, -1 if n(e)=v, and 0 otherwise, where e is the jth edge and v is the ith vertex.

For example, if G is the complete graph on 4 vertices, then one possibility for M(G) is:

               1   1   1   0   0   0  
              -1   0   0   1   1   0   
               0  -1   0  -1   0   1   
               0   0  -1   0  -1  -1

The particular matrix obtained depends on the orderings and the orientations chosen. In any case, the column sums are zero, the sums of the absolute values of the entries in each column are two, the sums of the absolute values of the entries in each row are the degrees of the vertices.

Theorem. For any graph G, the sum of the degrees of the vertices of G is twice the number of edges.

Proof. Add the absolute values of the entries of M(G), first across the rows (giving the degrees), and then add these numbers. Then add the absolute values of the entries of M(G), first down the columns (each giving the value two), and then add these |E| numbers.

If a graph G has n vertices, m edges and c components, then the rank of G is the rank of M(G) and this is n-c. The corank of G is m-n+c.

It is sometimes convenient to work with some field F other than the real numbers. Then, the cocyle space or bond space of G (over F) is the row space of M(G). The cycle space of G (over F) is the null space of M(G). The cycle space and the cocyle space are orthogonal, but for some choices of fields are not necessarily disjoint.

Two graphs G and H are isomorphic if and only if there are permutation matrices P and Q and a diagonal matrix D with diagonal entries from {1,-1} such that M(G)=PM(H)DQ.

A second matrix obtained from the graph is the augmented adjacency matrix, Aug(G). This is the |V| by |V| matrix obtained by multiplying M(G) by its transpose. The diagonal entries of the augmented adjacency matrix are the degrees of the vertices of G. For some applications, we may use the adjacency matrix, A(G), obtained by replacing the diagonal entries of the augmented adjacency matrix by zeroes. It is also clear that two graphs G and H are isomorphic if and only if there is a permutation matrix P, such that A(G)=PA(H)P^-1. We may now define the eigenvalues of a graph G to be the eigenvalues of the adjacency matrix, A(G). If two graphs are isomorphic, they have the same eigenvalues (and the same characteristic polynomial). However, there are pairs of non-isomorphic graphs with the same eigenvalues. For example, the complete bipartite graph K_1,4 and C₄+K₁ (the graph with two components, one of which is a 4-cycle, and the other a single vertex). The idiosyncratic polynomial is the characteristic polynomial of the matrix that results from replacing all zeroes in the adjacency matrix by some variable, y. (This is a two variable polynomial.)

The group of isomorphisms from a graph G to itself is the automorphism group of G, Aut(G). A graph G is vertex-transitive if Aut(G) acts transitively on V(G), and edge-transitive if Aut(G) acts transitively on E(G). A connected non-bipartite edge-transitive graph must be vertex-transitive. Lovász asked for an example of a connected vertex-transitive graph with no Hamilton path. Only six examples of connected vertex-transitive graphs without Hamilton cycles are known: the complete graphs on one or two vertices, the Petersen graph, the Coxeter graph, and two graphs obtained from the Petersen graph and the Coxeter graph by truncation at each vertex.

One can consider the Petersen graph, P, as having vertices labelled {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}, with two vertices being joined by an edge if their labels are disjoint. It is thus obvious that the automorphism group acts transitively on the vertex set, since each permutation in S₅ induces an automorphism of the graph. We see that there are at least 120 automorphisms. We also note that the stabilizer of any vertex v induces an automorphism on P-v, a 9-cycle with three chords, fixing the set N(v) as a set, not necessarily pointwise. One can then show that there are exactly two automorphisms which fix N(v) pointwise, and that there are automorphisms which rearrange N(v) in any of the six possible permutations. Thus, the automorphism group group has exactly 120 elements.

Now, consider any path in the Petersen graph, P, with four vertices and three edges. Let {1,2,3,4,5} = {i,j,k,λ,m}. Without loss of generality, the first vertex is {i,j} and the second vertex is {k,λ}. The third vertex must use two of the labels i,j,m, but not both of i,j. Without loss of generality, the third vertex is {i,m}. The fourth vertex must use two of the labels j,k,λ, but not both of k,λ. Without loss of generality, the third vertex is {j,k}. Hence, the path is, without any loss of generality, given by {i,j},{k,λ},{i,m},{j,k}. The automorphism of P induced by
θ(i)=1, θ(j)=2, θ(k)=3, θ(λ)=4, θ(m)=5, takes this path onto the path {1,2},{3,4},{5,1},{2,3}. Therefore the automorphism group of the Peteresen graph acts transitively on paths of length three. We say that the Petersen graph is 3-path-transitive.

Matrix Tree Theorem

The number of spanning trees of a graph on n vertices is the (absolute value of the) determinant of any n-1 by n-1 submatrix of the augmented adjacency matrix.

Proof. Let A be the augmented adjacency matrix of the graph G, where G has n vertices.. It is a fairly easy exercise to verify that rank(A)=n-w, where w is the number of components of G. Thus, if G is disconnected, any n-1 by n-1 minor is 0, and this is also the number of spanning trees of G. Therefore, we may assume that G is connected.

Now, since rank(A)=n-1, the null space of A has dimension one. However, AJ=0, where J is the vector of all ones. Thus, the null space of A is spanned by J. Now, let B denote the adjoint of A, that is, B is the matrix whose (i,j) entry is (0-1)^i+jA_ji, where A_ji is the minor that results from deleting row j and column i from A. But AB=det(A)I=0, and thus each column of B is in the null space of A. Thus, all entries in any column of B are identical.

Similarly, J^tA=0, and BA=0. Thus, all entries in any row of B are identical and, therefore, all entries of B are identical.

We need only show that this common entry is the number of spanning trees of G. For convenience, we consider the matrix C, the matrix that arises from deleting the last row and column of A. Let M be the incidence matrix of the graph G, where the vertex labels appear in the same order as they do for A, and let D be the matrix obtained by deleting the last row of M. As noted before, MM^t=A. Thus, DD^t = C.

Now (by the Binet-Cauchy theorem): det(C) = det(D_K₁)det(D_K₁ )^t+...+det(D_{K_q})det(D_{K_q} )^t, where each D_{K_i} denotes an n-1 by n-1 submatrix of D and the sum is over all such submatrices.

Thus, det(C) = det(D_K₁ )²+...+det(D_{K_q} )². We leave it as an easy exercise for the reader to show that det(D_K₁ ) = ±1 if the edges corresponding to the columns of D_K₁ comprise a spanning tree, and (D_K₁ ) = 0 otherwise. This completes the proof of the Matrix tree Theorem.

There is a slightly more general versison of the Matrix-Tree Theorem. Label the edges of the graph, e₁, e₂, ..., e_m. Now, let the adjaceny matrix A record these edges as follows. If the edges from v_i to v_j are e_a, e_b, ..., e_c, then the (i,j) entry of A is -e_a-e_b-...-e_c. If the edges meeting v_i are e_x, e_y, ..., e_z, then the (i,i) entry of A is e_x+e_y+...+e_z. Then, delete any row and any column of A, and take the determinant. The result will be (±) a list of the spanning trees of the graph. Again, if we agree to delete the last row and the last column, the sign will be positive.

It is obvious that setting e_k=1, for all k, reduces this new version to the Matrix-Tree Theorem shown above. This version helps lead one to another proof.

Let W be the diagonal matrix with entries e₁, e₂, ..., e_m. Then, A=MWM^t. Again, let C be the matrix that arises from deleting the last row and column of A, and let D be the matrix obtained by deleting the last row of M. As noted above, DWD^t = C.

Now (by the Binet-Cauchy theorem): det(C) = det(D_K₁)det(D_K₁ )^tP_K₁+...+det(D_{K_q})det(D_{K_q} )^tD_{K_q}, where each D_{K_i} denotes an n-1 by n-1 submatrix of D, P_{K_i} is the product of the e_j corrsponding to the choice of columns of D_{K_i}, and the sum is over all such submatrices.

We verify the statement of the Binet-Cauchy theorem. (Following the proof in van Lint and Wilson.)

Now, f=det(C) is a polynomial in the indeterminates e₁, e₂, ..., e_m, and every monomial of this polynomial has degree n-1. Pick any monomial g. Let f', g', C', and W' denote the values of f, g, C, and W upon replacing all indeterminates not present in g by 0.

Then, f'=g'. But, if g has fewer than n-1 indeterminants, then f'=0 , since W', and thus C', has rank less than n-1. Thus, all monomials of f must have n-1 distinct indeterminants.

Now, replace all indeterminants in g by 1, resulting in f", g", C", and W". Obviously, det(C")=det(D_K)det(D_K), where D_K is the n-1 by n-1 submatrix of D corresponding to the indeterminants in g. But, f"=det(C") is the coefficient of g in f.

For much more about algebraic properties of graphs, read the book Algebraic Graph Theory by N. Biggs. (This book has recently been updated and reprinted.)

Department of Mathematical Sciences
Florida Atlantic University
777 Glades Road
Boca Raton, Florida 33431-0991
USA

Office: Room 286, Science & Engineering
Phone: (561) 297-3350
Fax: (561) 297-2436
LockeS@fau.edu
URL: http://www.math.fau.edu/locke/graphmat.htm

Last modified May 3, 1999, by S.C. Locke.