> restart:with(linalg):with(networks):with(plots):

Warning, the protected names norm and trace have been redefined and unprotected

Warning, the names charpoly and rank have been redefined

Warning, the name changecoords has been redefined

When Professor Lambeau first announces the prize problem on the blackboard in the corridor, which is to be solved by Will the next evening, the blackboard in the classroom contains Parseval's Theorem from Fourier Analysis, as well as a part of its proof. Lambeau refers to the prize problem as an "advanced Fourier System" ,but it turns out to be a second year problem in algebraic graph theory, to be solved in four stages. Let's see, if Maple can do the job.

the multigraph G, its adjacency matrix A and the number of walks in G between two vertices.

> G:=graph({1,2,3,4},{}):addedge([{1,2},{1,4},{2,3},{2,3},{2,4}],weights=[1,1,1,1,1],names=[a,b,c,d,e],G);
draw(Concentric([2,4,1],[3]),G); ( the line 2--3 should be doubled)

A:=adjacency(G);

Its third power counts the walks of length three in G .

> evalm(A^3);

For instance the number 2 in the [1,1]-entry of A is equal to two because there are exactly two walks of lenght 3 from vertex 1 back to 1, viz. 1--2--4--1 and the other way around: 1--4--2--1.

To determine the nth power of A, which, of course, counts the n-steps walks in G and is not necessary for the solution of the problem we need to diagonalize our symmetric matrix A, but the eigenvalues (obtained in the classical way, according to Cardano) are complicated enough (see below) to not persue this goal any further.

> p(lambda):=charpoly(G,lambda);(linalg)[charpoly](A,lambda);factor(p(lambda));
q(lambda):=simplify(p(lambda)/(lambda+1));plot(q(lambda),lambda=-3..3);solve(q(lambda)=0);

> realroot(q(lambda),1/100);Digits:=20:fsolve(q(lambda),lambda=-2.4..-2.2);fsolve(q(lambda),lambda=0.6..0.7);fsolve(q(lambda),lambda=2.6..2.8);

An easier way to write the three eigenvalues is by using the three third roots of unity and the real-part function along the lines of Cardano's approach:

> lambda[1]:=(1+2*Re((-26+3*I*sqrt(687))^(1/3)))/3;
lambda[2]:=(1+2*Re(((-1+I*sqrt(3))/2)*(-26+3*I*sqrt(687))^(1/3)))/3;
lambda[3]:=(1+2*Re(((-1-I*sqrt(3))/2)*(-26+3*I*sqrt(687))^(1/3)))/3;
evalf(lambda[2],20);
evalf(lambda[3],20);
evalf(lambda[1],20);

Or, after normalizing to a complex number w of unit length and trisecting the appropriate angles:

> lambda[1]:='lambda[1]':lambda[2]:='lambda[2]':lambda[3]:='lambda[3]':
lambda:=n->(1+2*sqrt(19)*cos(phi(n)/3))/3;
w:=(-26+3*I*sqrt(687))/(19*sqrt(19));abs(w);phi:=n->arccos(-26/(19*sqrt(19)))+n*2*Pi;
for n from 1 by 1 to 3 do lambda[n]= evalf(lambda(n-1),20) od;

O.K. What you were waiting for; the experts do it as follows:

> solve(q(lambda)):evalc([%]);

> map(evalf(%),20);

So far the eigenvalues of A.

By the Cayley-Hamilton theorem we have the identity Aⁿ⁺⁴ = 7 Aⁿ⁺² + 2 Aⁿ⁺¹ - 4 Aⁿ, which allows for a recursive evaluation of the powers of A avoiding multiplication (almost) completely.

We finally note that the coefficients of the characteristic polynomial of any graph have a distinct interpretation in terms of sesquilinear subgraphs, that is, in terms of subgraphs whose components are either cycles or single edges; see e.g." Chapter 7 of Norman Biggs' Algebraic Graph Theory". In the case at hand the coefficient 7 can be explained as the number of edges of G counting the edges in the 2-cycle (through the vertices 2 and 3) twice. The next coefficient 2 stems from the fact that the single triangle in G has two orientations.

the generatingfunction f(z) for the number of walks between two arbitrary, but fixed, vertices of G; in particular the vertices 1 and 3.

> id:=(i,j)-> if i=j then 1 else 0 fi: I4:=matrix(4,4,id);evalm(z*A);n:='n':f(z):=Sum((evalm(z*A))^n,n=0..infinity); f(z):=evalm(inverse((I4-z*A)));

> factor(f(z)[1,3]);

> (-1)^(1-3)*det(minor(I4 - z*A,3,1))/det(I4 - z*A);

> simplify(%);

> taylor(f(z)[1,3],z=0,13);

> for i from 2 by 1 to 12 do evalm(A^i)[1,3] od;

two eigenvalue problems on the classroom blackboard.

> restart:with(linalg):B:=matrix(3,3,[[1,1,0],[1,1,-2],[2,1,0]]);
C:=matrix(3,3,[[2*k,-k,-k],[-k,2*k,-k],[-k,-k,2*k]]);

Warning, the protected names norm and trace have been redefined and unprotected

> charpoly(B,lambda);eigenvects(C);

the chromatic polynomial of a triangular graph, determined jointly by Lambeau and Will by simplifying a rational function for it.

While listening to a Mathematical Café talk by Hajo Broersma I realized where the rational function could come from. But let us first try the (trivial) elementary approach. There are k ways to color vertex 1 with a color from a colorset of size k and, in a proper vertex coloring, for each chosen color for vertex 1, vertex 2 can only be colored in k-1 ways, viz. with a color distinct from that picked out for 1. Now there are only k-2 admissible colors left for vertex 3 and so on, until we end up with P_H(k) = k(k-1)(k-2)⁴.

> restart:with(networks):H:=graph({1,2,3,4,5,6},{{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,6},{3,5},{3,6}}):draw(Concentric([1,2,3],[4,6,5]),H);

> chrompoly(H,k);

( = P_H(k), so Maple agrees.)

Click here for the rational function approach, based on a general lemma.

Cayley's theorem on the number of spanning trees in a complete graph.

> restart:with(networks):K4:=complete(4):draw(K4);
this graph has 16 spanning trees; the has , by Cayley's theorem. This number (answer?) is written on the top leftside of the blackboard, when Will is drawing his (irrelevant) trees beneath and Lambeau and Tom enter the corridor. Many distinct original proofs exist for Cayley's result; among them one by my colleague Frits Göbel.