Fix an edge \(\{ x,y\} \). Since \(G\) has no isolated vertices, every vertex \(v\) is an endpoint of some edge \(e\), and by edge-transitivity there is \(f\in \mathrm{Aut}(G)\) with \(\{ f(x),f(y)\} =e\); hence \(v\in \{ f(x),f(y)\} \), so \(v\) lies in the \(\mathrm{Aut}(G)\)-orbit \(X\) of \(x\) or the orbit \(Y\) of \(y\). Thus \(V(G)=X\cup Y\) and there are at most two vertex orbits.

If \(X=Y\) (some automorphism sends \(x\) to \(y\)) then \(\mathrm{Aut}(G)\) has a single vertex orbit, so \(G\) is vertex-transitive. Otherwise \(X\) and \(Y\) are distinct orbits, hence disjoint, and partition \(V(G)\). Every edge is the image \(\{ f(x),f(y)\} \) of \(\{ x,y\} \) under some \(f\in \mathrm{Aut}(G)\), and \(f(x)\in X\), \(f(y)\in Y\); therefore every edge joins \(X\) to \(Y\), so \(G\) is bipartite with parts \(X,Y\).

An automorphism \(f\) is an edge-preserving bijection, so it maps the neighbours of \(u\) bijectively onto the neighbours of \(f(u)\); hence \(d_u=d_{f(u)}\). If \(G\) is vertex-transitive, for any \(u,v\) some automorphism sends \(u\) to \(v\), so \(d_u=d_v\). Thus every vertex has the same degree.

Let \(T=\operatorname {diag}(d_v)\) be the diagonal degree matrix. By definition \(\mathcal{L}= T^{-1/2}(T-A)T^{-1/2} = I - T^{-1/2}AT^{-1/2}\). For a \(k\)-regular graph \(T=kI\), so \(T^{-1/2}=k^{-1/2}I\) and \(T^{-1/2}AT^{-1/2}=\tfrac 1k A\), giving \(\mathcal{L}= I-\tfrac 1k A\). A vertex-transitive graph is regular by Lemma 271.

Let \(\Gamma \) be \(k\)-regular on \(n=|V(\Gamma )|\) vertices, so \(\operatorname {vol}\Gamma =kn\) and \(\operatorname {vol}S=k|S|\) for \(S\subseteq V(\Gamma )\). Let \(S\) be a subset with \(\operatorname {vol}S\le \operatorname {vol}\bar S\), i.e. \(|S|\le n/2\). Choose an ordered pair of vertices \((x,y)\) uniformly over \(V(\Gamma )\times V(\Gamma )\), and then a shortest path \(P\) between \(x\) and \(y\) uniformly among all shortest \(x\)–\(y\) paths.

For an edge \(e\) let \(p(e)=\Pr [e\in P]\). The whole experiment is invariant under \(\mathrm{Aut}(\Gamma )\), so edge-transitivity forces \(p(e)\) to be the same for every edge. Since the length of \(P\) equals \(d(x,y)\le D\),

and as all \(|E(\Gamma )|=\operatorname {vol}\Gamma /2\) edges share the common value \(p(e)\),

If exactly one of \(x,y\) lies in \(S\) then \(P\) must use an edge of the cut \(E(S,\bar S)\). Hence

Therefore \(|E(S,\bar S)| \ge \dfrac {|S|\, |\bar S|\, \operatorname {vol}\Gamma }{D\, n^2}\), and

Taking the minimum over \(S\) gives \(h_\Gamma \ge 1/(2D)\).

Let \(W\) be the set of vertices incident to at least one edge of \(E_i\). Since \(E_i\) is \(\mathrm{Aut}(\Gamma )\)-invariant, so is \(W\); as \(\mathrm{Aut}(\Gamma )\) acts transitively on \(V(\Gamma )\) and \(W\neq \emptyset \), we get \(W=V(\Gamma )\). Thus every vertex is incident to some edge of \(E_i\). Counting vertex–edge incidences within \(E_i\) gives \(2|E_i| = \sum _{e\in E_i}2 \ge |V(\Gamma )| = n\), so \(|E_i|\ge n/2\).

As in the proof of Theorem 273, pick \((x,y)\) uniformly over \(V(\Gamma )\times V(\Gamma )\) and a uniform shortest path \(P\); for an edge \(e\) set \(p(e)=\Pr [e\in P]\). The experiment is \(\mathrm{Aut}(\Gamma )\)-invariant, so \(p(e)\) is constant on each edge orbit \(E_i\); call the common value \(p_i\). Since \(\sum _{e\in E_i}p(e)=|E_i|p_i\le \sum _{e}p(e)=\mathbb E[d(x,y)]\le D\), and \(|E_i|\ge n/2\) by Lemma 275, we obtain

For \(S\) with \(\operatorname {vol}S\le \operatorname {vol}\bar S\) (so \(|S|\le n/2\)), if exactly one of \(x,y\) lies in \(S\) then \(P\) crosses the cut, so

Hence \(|E(S,\bar S)| \ge \dfrac {|S|\, |\bar S|}{Dn}\) and, using \(\operatorname {vol}S=k|S|\),

Therefore \(h_\Gamma \ge 1/(2kD)\).

Writing \(P\) as \(x=u_0,u_1,\dots ,u_\ell =y\), we telescope \(f(x)-f(y)=\sum _{i=1}^{\ell }\bigl(f(u_{i-1})-f(u_i)\bigr)\). Each summand has absolute value \(f(e_i)\) where \(e_i=\{ u_{i-1},u_i\} \), so by Lemma 279, \((f(x)-f(y))^2\le \ell \sum _{i=1}^{\ell }(f(u_{i-1})-f(u_i))^2 =\ell \sum _{e\in P}f(e)^2\).

Use the harmonic (variational) form of \(\lambda _1\) from Chapter 1, eq. (1.5), valid for a \(k\)-regular graph:

For each edge \(e=\{ x,y\} \) set \(f(e)=|f(x)-f(y)|\), so the numerator is \(n\sum _{e\in E}f(e)^2\).

Let \(E_i\) be the edge classes under \(\mathrm{Aut}(\Gamma )\). Fix \(x_0\) and a set of shortest paths \(P_{x_0,y}\) to every \(y\). For each vertex \(x\) choose \(\pi _x\in \mathrm{Aut}(\Gamma )\) with \(\pi _x(x_0)=x\) and put \(P(x)=\{ \pi _x(P_{x_0,y}) : y\in V(\Gamma )\} \), a family of \(n\) paths each of length \(\le D\). For an edge \(e\) let \(N_e\) be the number of occurrences of \(e\) in the paths of \(\bigcup _x P(x)\). Two edges in the same class have the same \(N_e\), and the total number of edge occurrences is at most \(n\cdot nD=n^2D\), so for \(e\in E_i\),

For each ordered pair \((x,y)\) let \(P(x,y)\in P(x)\) be the chosen \(x\)–\(y\) path. By Lemma 280, \((f(x)-f(y))^2\le D\sum _{e\in P(x,y)}f(e)^2\). Summing over all pairs,

Substituting into the variational formula,

An edge-transitive graph is vertex-transitive (or bipartite; Lemma 266) and has a single edge orbit, so \(\operatorname {index}\Gamma =1\). Substituting into Theorem 281 gives \(\lambda _1\ge 1/D^2\).

By Definition 274, \(\operatorname {index}\Gamma \le k\). Substituting this into Theorem 281 gives \(\lambda _1\ge 1/(D^2\operatorname {index}\Gamma )\ge 1/(kD^2)\).

For \(x,y\in V_i\) we have \(d(v,x)=d(v,y)=i\), so by distance transitivity there is an automorphism fixing \(v\) and mapping \(x\) to \(y\); hence the stabiliser of \(v\) acts transitively on each \(V_i\). Starting from any eigenfunction \(f_0\) for \(\lambda \), the function \(f(x)=\frac{1}{|\mathrm{Stab}(v)|}\sum _{\sigma } f_0(\sigma x)\) obtained by averaging over the stabiliser is again an eigenfunction for \(\lambda \) (a group average of eigenfunctions, using that \(\mathcal{L}\) commutes with automorphisms), and it is constant on each \(V_i\). For a suitable choice of \(v\) (with \(f_0(v)\neq 0\)) this average is not identically zero.

Let \(\lambda \) be an eigenvalue of \(\Gamma \). By Lemma 285 there is an eigenfunction \(f\) for \(\lambda \) that is constant on each \(V_i\); choosing \(v\) with \(f(v)\neq 0\) and mapping \(v\) to \(v_0\), assign to \(v_i\) the common value of \(f\) on \(V_i\). This function on \(P\) is not identically zero, and the weights of \(P\) are exactly the coefficients with which \(\mathcal{L}\) acts on functions constant on the \(V_i\); hence it is a harmonic eigenfunction of \(P\) for \(\lambda \). Thus every eigenvalue of \(\Gamma \) is an eigenvalue of \(P\). The converse (every eigenvalue of \(P\) is an eigenvalue of \(\Gamma \)) is Theorem 288.

Let \(f\) be a harmonic eigenfunction of \(P\) with eigenvalue \(\lambda \), so \((\mathcal{L}_P f)(v_i)=\lambda f(v_i)\), i.e.

where \(c_i,a_i,b_i\) are the intersection numbers of Construction 286. Define \(g:V(\Gamma )\to \mathbb {R}\) by \(g(x)=f(v_i)\) for \(x\in V_i\). For \(x\in V_i\) its \(k\) neighbours split into \(c_i\) in \(V_{i-1}\), \(a_i\) in \(V_i\), \(b_i\) in \(V_{i+1}\), so

Hence \(\mathcal{L}g=\lambda g\) and \(g\) is an eigenfunction of \(\Gamma \) for \(\lambda \).

The intersection numbers of Construction 286 give the distance-regular recurrence \(A\, A_j = c_{j+1}A_{j+1}+a_j A_j + b_{j-1}A_{j-1}\) with \(c_{j+1}{\gt}0\). Solving for \(A_{j+1}\) shows by induction that \(A_{j}\) is a polynomial in \(A\) of exact degree \(j\) (leading term \(A^{j}/\prod _{l\le j}c_l\)). The matrices \(A_0,\dots ,A_D\) have pairwise disjoint supports (the pair \((x,y)\) contributes to \(A_{d(x,y)}\) only), hence are linearly independent; since each \(A_j\) is a degree-\(j\) polynomial in \(A\), the powers \(I,A,\dots ,A^{D}\) span the same space and are therefore linearly independent as well.

By Theorems 287 and 288 the eigenvalues of \(\Gamma \) coincide with those of the \((D+1)\)-vertex path \(P\), so there are at most \(D+1\) distinct eigenvalues. Conversely, suppose there were only \(d\le D\) distinct eigenvalues \(\lambda _1,\dots ,\lambda _d\). Then \(\prod _{\lambda _i\ \text{distinct}}(\mathcal{L}-\lambda _i I)=0\), a polynomial relation of degree \(d\) among \(I,\mathcal{L},\mathcal{L}^2,\dots ,\mathcal{L}^{d}\); since \(\mathcal{L}=I-\tfrac 1kA\) (Lemma 272) this is a relation of degree \(d\le D\) among \(I,A,\dots ,A^{D}\), contradicting their independence (Lemma 289). Hence there are at least, and so exactly, \(D+1\) distinct eigenvalues.

Theorem 287 already produces the path \(P\) by contracting the distance classes \(V_i\) about a fixed \(v\), and together with Theorem 288 shows the eigenvalue sets coincide. By Theorem 290 both have exactly \(D+1\) distinct values; as \(P\) has \(D+1\) vertices its eigenvalues are simple, while those of \(\Gamma \) carry the multiplicities computed in Theorem 293.

Since \(A_j\) is a polynomial in \(A\) (Lemma 289), any eigenfunction of \(A\) is an eigenfunction of \(A_j\). By Theorem 288 a harmonic eigenfunction \(f\) of \(P\) lifts to the eigenfunction of \(A\) that takes the value \(f(v_i)\) on \(V_i\); write \(\lambda '\) for its \(A_j\)-eigenvalue. Let \(\pi \) be the projection \(V(\Gamma )\to V(P)\), viewed as a matrix with \(\pi (v_i,x)=1\) iff \(x\in V_i\), so \((\pi f)(v_i)=\sum _{x\in V_i}f(x)=|V_i|f(v_i)\), and let \(\phi _0=(1,0,\dots ,0)\) of length \(D+1\). Then, using \(A_j f=\lambda ' f\),

because \(|V_0|=1\). On the other hand \(\langle \phi _0,\pi A_j f\rangle \) picks out the \(v_0\)-coordinate of \(\pi A_j f\), which is \(\sum _{y:\, d(v,y)=j}f(y)=|V_j|f(v_j)\). Equating gives \(\lambda ' = |V_j|f(v_j)/f(v_0)\).

Let \(g_0,\dots ,g_D\) be the (simple, orthogonal) eigenfunctions of \(P\) and \(f_0,\dots ,f_D\) the corresponding lifted harmonic eigenfunctions, normalised so that \(g(v_i)=\sqrt{k|V_i|}\, f(v_i)\). Consider the \(n\times n\) matrix

Only \(A_0=I\) has nonzero diagonal, so \(\operatorname {tr}M_i = f_i(v_0)\operatorname {tr}I = n f_i(v_0)\), which is equation (7.3):

On the other hand, by Theorem 292 the eigenvalues of \(A_j\) are \(|V_j|f_l(v_j)/f_l(v_0)\) with multiplicity \(m(\lambda _l)\), so

Distinct eigenfunctions are orthogonal: \(\sum _{i}f_p(v_i)f_q(v_i)|V_i|\, k = 0\) if \(p\neq q\) and \(=\| g_p\| ^2\) if \(p=q\). Hence the inner sum is \(\delta _{il}\| g_i\| ^2/k\), and

Since \(|V_0|=1\) we have \(g^2(v_0)=k f^2(v_0)\), giving \(m(\lambda )=\dfrac {n}{\| g\| ^2}\, g^2(v_0)\).

Being distance transitive of diameter \(D=2\), the Petersen graph has exactly \(D+1=3\) distinct eigenvalues (Theorem 290). Contracting the distance classes \(|V_0|=1,\ |V_1|=3,\ |V_2|=6\) into the weighted path on \(3\) vertices (Theorem 287) yields the adjacency eigenvalues \(3,1,-2\). The Gelfand-pair decomposition (Proposition 295) with \(n=5,r=2\) gives eigenspace dimensions \(\dim E_0=1\), \(\dim E_1=\binom 51-\binom 50=4\), \(\dim E_2=\binom 52-\binom 51=5\), so the adjacency multiplicities are \(3^{(1)},1^{(4)},(-2)^{(5)}\). Since the graph is \(3\)-regular, \(\mathcal{L}=I-\tfrac 13A\) (Lemma 272) sends these to \(0^{(1)}\), \(\tfrac 23^{(5)}\) (from \(A\)-eigenvalue \(1\) on \(E_2\), dimension \(5\)), and \(\tfrac 53^{(4)}\) (from \(A\)-eigenvalue \(-2\) on \(E_1\), dimension \(4\)).

The adjacency operator of \(\Gamma \) on \(\mathbb {C}[\mathcal H]\) is \(A=\sum _{g\in \mathcal K}R(g)\), where \(R(g)\) is the permutation matrix of right translation by \(g\); thus \(A\) acts as the regular representation evaluated on \(\sum _{g\in \mathcal K}g\), and \(\mathcal{L}=I-\tfrac 1kA\) (Lemma 272). By Lemma 297 the regular representation splits as \(\bigoplus _\rho (\dim \rho )\, \rho \). On the \(\rho \)-isotypic component the operator \(\sum _{g\in \mathcal K}R(g)\) acts as \(\bigl(\sum _{g\in \mathcal K}\rho (g)\bigr)\otimes I_{\dim \rho }\); hence \(\mathcal{L}\) restricts there to \(\bigl(I-\tfrac 1k\sum _{g\in \mathcal K}\rho (g)\bigr)\otimes I_{\dim \rho }\). Therefore each eigenvalue of the \(\dim \rho \times \dim \rho \) matrix \(I-\tfrac 1k\sum _{g\in \mathcal K}\rho (g)\) is an eigenvalue of \(\mathcal{L}\) with multiplicity \(\dim \rho \), and ranging over all irreducibles exhausts the spectrum.

With \(\mathcal H=\mathbb {Z}_n\), \(\mathcal K=\{ 1,n-1\} \) and \(k=2\), each \(\rho _k\) is \(1\)-dimensional, so the block \(I-\tfrac 1k\sum _{g\in \mathcal K}\rho _k(g)\) of Theorem 298 is the scalar

Ranging over \(k=0,\dots ,n-1\) gives all \(n\) eigenvalues.

The displacement space \(\mathcal F(V,\mathbb {R}^3)\) is \(60\times 3=180\)-dimensional and equals (regular representation) \(\otimes \) (\(3\)-dimensional). By Lemma 297 the regular representation of \(A_5\) contains each irreducible with multiplicity equal to its dimension, hence has \(1+3+3+4+5=16\) irreducible constituents. Tensoring with the \(3\)-dimensional representation multiplies the number of constituents by \(3\), giving \(3\times 16=48\).

Rigid displacements of the whole molecule form a \(6\)-dimensional space, carrying two \(3\)-dimensional representations (translations and rotations). Subtracting these from the \(180\)-dimensional displacement space leaves \(174\) vibrational dimensions, and subtracting the two corresponding \(3\)-dimensional constituents from the \(48\) of Proposition 306 leaves at most \(46\) distinct modes.