4 4. Paths, flows, and routing
Throughout this chapter \(G=(V,E)\) is a graph on \(n\) vertices with (normalized) eigenvalues \(0=\lambda _0\le \lambda _1\le \cdots \le \lambda _{n-1}\), spectral gap \(\lambda _1\), and volume \(\operatorname {vol}G=\sum _v d_v\). Flows and routes are used to obtain lower bounds for Cheeger constants and eigenvalues, and conversely good eigenvalue bounds are used to construct short routes of small congestion.
Let \(G\) be a graph with vertex set \(V\) and edge set \(E\), and let \(X\) and \(Y\) be two equinumerous (multi)subsets of \(V\) with \(|X|=|Y|=m\) (not necessarily disjoint). A flow \(F\) from \(X\) to \(Y\) consists of \(m\) paths in \(G\) joining the vertices of \(X\) to the vertices of \(Y\) in a one-to-one fashion. The multiset \(X\) is the input of \(F\) and \(Y\) its output. The paths are typically required to be edge-disjoint or vertex-disjoint, or, more generally, to have small congestion: no edge (or vertex) of \(G\) should be used by too many paths of \(F\).
A route set is a flow together with a specified input–output assignment \(A=\{ (x_i,y_i):x_i\in X,\ y_i\in Y\} \): it consists of paths \(P_i\) joining \(x_i\) to \(y_i\) for each \(i\). Thus an assignment specifies “who is talking to whom.”
A routing \(R\) is a dynamic version of a route set, defined as a pebble game. Initially a pebble \(p_i\) is placed at each input vertex \(x_i\), with destination \(y_i\), for each assignment \((x_i,y_i)\in A\). At each time unit a pebble may be moved to an adjacent vertex. The routing \(R\) is a route set together with a strategy for moving the pebbles to their destinations; additional requirements (e.g. at each time unit the edges used are vertex- or edge-disjoint, or all edges have small congestion) may be imposed.
Let \(f\colon V\to \mathbb {R}\) and let \(P\) be a walk from \(x\) to \(y\) whose edge set \(P\) has \(|P|\) edges. Writing \(f^2(e)=(f(a)-f(b))^2\) for an edge \(e=\{ a,b\} \), we have
Orient \(P\) from \(x\) to \(y\); then \(f(x)-f(y)=\sum _{e=\{ a,b\} \in P}\bigl(f(a)-f(b)\bigr)\) is a telescoping sum with \(|P|\) terms. By Lemma 65 with \(r=|P|\), \(\bigl(\sum _{e\in P}(f(a)-f(b))\bigr)^2\le |P|\sum _{e\in P}(f(a)-f(b))^2=|P|\sum _{e\in P}f^2(e)\).
For a graph \(G\) on \(n\) vertices, suppose there is a set of \(\binom {n}{2}\) paths joining all pairs of vertices such that each edge of \(G\) is contained in at most \(m\) of the paths. Then
Fix \(S\subseteq V\) with \(|S|\le |\bar S|\). Each of the \(|S|\cdot |\bar S|\) pairs \((x,y)\) with \(x\in S,\ y\in \bar S\) is joined by a path in the family, and that path must use at least one edge of the cut \(E(S,\bar S)\). Since each cut edge lies in at most \(m\) of the paths,
using \(|\bar S|\ge n/2\). Hence \(\dfrac {|E(S,\bar S)|}{\min (|S|,|\bar S|)}=\dfrac {|E(S,\bar S)|}{|S|}\ge \dfrac {n}{2m}\) for every \(S\), and the infimum is \(\ge n/2m\).
For a \(k\)-regular graph \(G\) on \(n\) vertices, suppose there is a set \(P\) of \(\binom {n}{2}\) paths joining all pairs of vertices such that each edge of \(G\) is contained in at most \(m\) paths in \(P\). Then the Cheeger constant satisfies
For a \(k\)-regular graph \(\operatorname {vol}S=k|S|\), so \(h_G=h'_G/k\). The bound follows from Lemma 138.
For a \(k\)-regular graph \(G\) on \(n\) vertices, suppose there is a set \(P\) of \(\binom {n}{2}\) paths joining all pairs of vertices such that each path in \(P\) has length at most \(l\) and each edge of \(G\) is contained in at most \(m\) paths in \(P\). Then
Let \(f\colon V\to \mathbb {R}\) be the harmonic eigenfunction achieving \(\lambda _1\), so \(\sum _x f(x)=0\). Since \(\sum _{\{ x,y\} }(f(x)-f(y))^2=n\sum _x f^2(x)-\bigl(\sum _x f(x)\bigr)^2=n\sum _x f^2(x)\) (the sum over unordered pairs), the Rayleigh characterization gives
For a pair \(x,y\) with joining path \(P(x,y)\), Lemma 137 gives \((f(x)-f(y))^2\le |P(x,y)|\sum _{e\in P(x,y)}f^2(e)\le l\sum _{e\in P(x,y)}f^2(e)\), where \(f^2(e)=(f(a)-f(b))^2\) for \(e=\{ a,b\} \). Summing over all pairs and using that each edge lies in at most \(m\) paths,
Hence \(\sum _{e\in E(G)}f^2(e)\ge \frac{1}{ml}\sum _{\{ x,y\} }(f(x)-f(y))^2\), and therefore
For an undirected graph \(G\) with \(e=|E(G)|\), replace each edge \(\{ u,v\} \) by the two directed edges \((u,v),(v,u)\). Suppose there is a set \(P\) of \(4e^2\) directed paths such that for each ordered pair of directed edges there is a directed path in \(P\) joining them, and each directed edge of \(G\) lies in at most \(m\) paths of \(P\). Then
Fix \(S\) with \(\operatorname {vol}S\le \operatorname {vol}\bar S\). There are exactly \(\operatorname {vol}S\) directed edges with tail in \(S\) and \(\operatorname {vol}\bar S\) directed edges with tail in \(\bar S\). Consider the \(\operatorname {vol}S\cdot \operatorname {vol}\bar S\) ordered pairs \((a,b)\) where \(a\) has tail in \(S\) and \(b\) has tail in \(\bar S\). The directed path in \(P\) joining \(a\) to \(b\) starts at a vertex of \(S\) (the tail of \(a\)) and passes through a vertex of \(\bar S\) (the tail of \(b\)), so it uses at least one directed edge crossing from \(S\) to \(\bar S\); there are exactly \(|E(S,\bar S)|\) such crossing edges, each in at most \(m\) paths. Hence
using \(\operatorname {vol}\bar S\ge \operatorname {vol}G/2\). Dividing by \(\operatorname {vol}S=\min (\operatorname {vol}S,\operatorname {vol}\bar S)\) gives \(h_G\ge \operatorname {vol}G/(2m)\).
For an undirected graph \(G\) with \(e=|E(G)|\), replace each edge \(\{ u,v\} \) by the two directed edges \((u,v),(v,u)\). Suppose there is a set \(P\) of \(4e^2\) directed paths such that for each ordered pair of directed edges there is a directed path in \(P\) joining them, each of length at most \(l\), and each directed edge of \(G\) lies in at most \(m\) paths of \(P\). Then
A random walk of length \(l\) starting at a vertex \(v\) is a randomly chosen sequence \(v=v_0,v_1,\dots ,v_l\), where each \(v_{i+1}\) is chosen uniformly at random and independently among the neighbors of \(v_i\), for \(i=0,\dots ,l-1\); the walk visits \(v_i\) at time \(i\). Equivalently, the transition matrix is \(P(u,v)=1/d_u\) if \(u\sim v\) and \(0\) otherwise, so \(P=T^{-1}A\) with \(T=\operatorname {diag}(d_v)\).
Let \(E_1,\dots ,E_M\) be independent events with \(\Pr [E_i]=p_i\) and \(\sum _i p_i\le \gamma \). Then for every positive integer \(s\),
If at least \(s\) events occur then some \(s\)-subset all occur; by the union bound and independence, \(\Pr [\text{at least }s]\le \sum _{|S|=s}\prod _{i\in S}p_i=e_s(p)\), the \(s\)-th elementary symmetric function. Comparing with the multinomial expansion of \((\sum _i p_i)^s\) (each squarefree monomial appears \(s!\) times, all terms nonnegative) gives \(e_s(p)\le \frac{1}{s!}(\sum _i p_i)^s\le \frac{\gamma ^s}{s!}\). Finally \(s!\ge (s/e)^s\), so \(\frac{\gamma ^s}{s!}\le \gamma ^s(e/s)^s=(\gamma e/s)^s\).
Let \(G\) be a graph on \(n\) vertices and suppose \(l\ge \log n/\lambda _1\). Suppose for each \(v\in V(G)\) there are \(d_v\) walks of length \(l\) starting at \(v\). For any edge \(q\) let \(I(q)\) be the total number of these walks containing \(q\). Then almost surely (with probability tending to \(1\) as \(n\to \infty \)) there is no edge \(q\) with \(I(q){\gt}10l\).
Let \(P=T^{-1}A\) be the transition matrix, \(T=\operatorname {diag}(d_v)\), and let \(\psi _y\) be the unit coordinate vector at \(y\). The probability that a walk starting at \(x\) visits \(y\) at time \(i\) is \(\psi _x P^i\psi _y^{*}\), and the probability that it visits \(u\) at time \(i\) and \(v\) at time \(i+1\) (traversing the directed edge \((u,v)\)) is \(\psi _x P^i\psi _u^{*}/d_u\). With \(d_x\) walks starting at each \(x\), the expected number of walks traversing \(q=\{ u,v\} \) is at most
Since \(\mathbf1T\) is stationary, \((\mathbf1T)P^i=\mathbf1T\), and \(\mathbf1T\psi _u^{*}=d_u\); hence \(\mathbb {E}\, I(q)\le \sum _{i=0}^{l-1}1=l\). Now \(I(q)\) is a sum of \(\operatorname {vol}G=\sum _v d_v\) independent indicator variables (one per walk) with \(\sum _i p_i=\mathbb {E}\, I(q)\le l\). Applying Lemma 144 with \(\gamma =l\) and \(s=10l\),
There are at most \(n^2\) edges, so by the union bound the probability that some edge has \(I(q){\gt}10l\) is \(\ll 1/n\), which tends to \(0\).
Let \(G\) be a graph on \(n\) vertices and let \(A=\{ (x_i,y_i):x_i\in X,\ y_i\in Y\} \) be any assignment in which each vertex \(v\) occurs in \(X\) with multiplicity \(d_v\) and in \(Y\) with multiplicity \(d_v\). Then there are paths \(P_i\) joining \(x_i\) to \(y_i\), each of length at most \(\frac{20}{\lambda _1}\log n\), such that each edge of \(G\) is contained in at most \(\frac{20}{\lambda _1}\log n\) of the paths.
Let \(P_i\) be a random walk of length \(2l\) between \(x_i\) and \(y_i\) with \(l\approx \frac{\log n}{\lambda _1}\). By Valiant’s routing argument we may take each such walk to consist of two independent random walks of length \(l\), one from \(x_i\) and one from \(y_i\): since \(l\ge \log n/\lambda _1\), the distribution of a length-\(l\) walk is close to the stationary distribution, so \(P_i\) may be viewed as chosen by first selecting its midpoint according to the stationary distribution and then choosing its two halves. Applying Theorem 145 to each half (there are \(\sum _v d_v\) walks in each family) bounds the length by \(2l\le \frac{20}{\lambda _1}\log n\) and the congestion of any edge by \(20l\le \frac{20}{\lambda _1}\log n\).
Let \(G\) be a \(k\)-regular graph on \(n\) vertices and let \(\pi \) be a permutation of its vertices. Then there are paths \(P_x\) joining \(x\) to \(\pi (x)\) of length at most \(\frac{2}{\lambda _1}\log n\) such that each edge of \(G\) is contained in at most \(\frac{20}{k\lambda _1}\log n\) paths.
Let \(G=(V,E)\) be connected, \(|V|=n\). Initially each vertex \(v\) carries a distinct pebble \(p_v\) with destination \(\pi (v)\in V\), where \(\pi \) is a permutation. At each step a disjoint set of edges is chosen and the pebbles at the two endpoints of each chosen edge are interchanged. Let \(p_v(t)\) be the location at time \(t\) of the pebble that started at \(v\); \(\{ p_v(t):v\in V\} \) is always a permutation of \(V\). Let \(rt(G,\pi )\) be the minimum number of steps needed to realize \(\pi \), and define the routing number
Equivalently, \(rt(G)\) is the largest number \(r\) of factors needed to write some permutation of \(S_n\) as a product \((u_1v_1)(u_2v_2)\cdots (u_rv_r)\) where each factor is a product of disjoint transpositions along edges of \(G\).
For every connected graph \(G\) and every permutation \(\pi \), \(rt(G,\pi )\) is finite; hence \(rt(G)\) is well defined.
Fix a spanning tree \(T\) of \(G\) and induct on \(n=|V|\). Let \(u\) be a leaf of \(T\) and let \(p\) be the pebble whose destination is \(u\). Route \(p\) along the (finite) tree path to \(u\) in finitely many steps, then leave \(u\) fixed and complete the routing of the remaining pebbles on \(T\setminus \{ u\} \) by induction. This uses finitely many steps, so \(rt(G,\pi ){\lt}\infty \).
For every connected graph \(G\), \(rt(G)\ge D(G)\), where \(D(G)\) is the diameter.
Each step moves any single pebble to an adjacent vertex, so the distance from a pebble to its destination decreases by at most \(1\) per step. Choose \(u,w\) with \(d(u,w)=D(G)\) and a permutation \(\pi \) with \(\pi (u)=w\); the pebble at \(u\) needs at least \(D(G)\) steps, so \(rt(G,\pi )\ge D(G)\) and hence \(rt(G)\ge D(G)\).
For the path \(P_n\) on \(n\) vertices, \(rt(P_n)=n\). Any permutation of \(P_n\) can be sorted in \(n\) steps by odd–even transposition sort: label consecutive edges \(e_1,\dots ,e_{n-1}\) and, on even (resp. odd) steps, interchange along the even edges \(e_{2k}\) (resp. odd edges \(e_{2k+1}\)).
For the complete graph \(K_n\), \(rt(K_n)=2\); moreover every permutation of \(S_n\) is a product of at most two permutations, each a product of disjoint transpositions along edges of \(K_n\).
For the complete bipartite graph \(K_{n,n}\) with \(n\ge 3\), \(rt(K_{n,n})=4\).
For every tree \(T_n\) on \(n\) vertices, \(rt(T_n){\lt}3n\).
For the \(n\)-cube \(Q_n\), \(rt(Q_n)\le 2n-1\). Also \(rt(Q_n)\ge n\) (its diameter), with \(rt(Q_n)\ge n+1\) for \(n=2,3\).
For the \(m\times n\) grid \(P_m\times P_n\) with \(m\le n\), \(rt(P_m\times P_n)\le 2m+n\).
For graphs \(G,G'\), \(rt(G\times G')\le 2\, rt(G)+rt(G')\), and by symmetry
Any graph of maximum degree at most \(\Delta \) is \((\Delta +1)\)-colorable.
Order the vertices arbitrarily and color them one at a time. When coloring a vertex it has at most \(\Delta \) already-colored neighbors, so at most \(\Delta \) colors are forbidden and one of the \(\Delta +1\) colors is available.
Let \(G\) be a regular graph on \(n\) vertices and \(l\ge \log n/\lambda _1\). For each \(v\in V\) independently, let \(W(v)\) be a random walk of length \(l\) starting at \(v\). Let \(I(v)\) be the number of other walks \(W(u)\) for which there exist a vertex \(x\) and indices \(0\le i,j\le l\) with \(|i-j|{\lt}5\) such that \(W(v)\) visits \(x\) at time \(i\) and \(W(u)\) visits \(x\) at time \(j\). Then almost surely there is no vertex \(v\) with \(I(v){\gt}100l\).
Let \(G\) be a regular graph on \(n\) vertices and let \(\sigma \) be a permutation of order two on \(V\) (a product of disjoint transpositions). Put \(l=\frac{10}{\lambda _1}\log n\). Then there is a system of \(n\) walks \(W(v)\), \(v\in V\), each of length \(2l\), such that both \(W(v)\) and \(W(\sigma (v))\) connect \(v\) and \(\sigma (v)\) and traverse the same edge set (in opposite directions), and such that, letting \(I(v)\) be the number of other walks \(W(u)\) for which there exist \(x\) and indices \(0\le i,j\le l\) with \(|i-j|{\lt}5\) so that \(W(v)\) visits \(x\) at time \(i\) and \(W(u)\) visits \(x\) at time \(2l-j\), one has \(I(v)\le 400l\) for all \(v\).
Let \(\sigma \) be a permutation of the vertex set of a regular graph \(G\) on \(n\) vertices. Then
By Proposition 152 every permutation is a product of at most two permutations of order two, so it suffices to treat \(\sigma \) of order two. Set \(l=\frac{10}{\lambda _1}\log n\); we show \(rt(G,\sigma )=O(l^{2})\). Take the walk system \(W(v)\) of length \(2l\) provided by Theorem 160. Form the collision graph \(H\) on these walks, joining \(W(u)\) and \(W(v)\) when there exist a vertex \(x\) and indices \(0\le i,j\le l\) with \(|i-j|{\lt}5\) such that \(W(v)\) visits \(x\) at time \(i\) and \(W(u)\) visits \(x\) at time \(2l-j\). By Theorem 160 the maximum degree of \(H\) is \(O(l)\), so by Lemma 158 \(H\) is \(O(l)\)-colorable; this splits the walks into \(O(l)\) classes, each an independent set of \(H\). For each class, perform \(2l\) steps in which steps numbered \(i\) and \(2l+1-i\) flip the pebbles along the \(i\)-th and \((2l+1-i)\)-th edges of each walk in the class, \(1\le i\le l\). After these \(2l\) steps the two ends of each walk have exchanged pebbles and, by the symmetry of the schedule, every other pebble has returned to its original place. Repeating over all \(O(l)\) classes routes \(\sigma \) in \(O(l)\cdot 2l=O(l^{2})=O\bigl(\lambda _1^{-2}\log ^{2}n\bigr)\) steps.
Let \(G=(V,E)\) be connected on \(n\) vertices. For a permutation \(\pi \), a route set \(P\) is a set of paths \(P_i\) joining each \(v_i\) to \(\pi (v_i)\). For an edge \(e\), let \(rc(e,G,\pi ,P)\) be the number of paths of \(P\) containing \(e\). The route covering number is
For any permutation \(\pi \) of a connected graph \(G\) and any route set \(P\) realizing \(\pi \),
so \(rc(G)\ge \max _\pi \dfrac {\sum _v d(v,\pi (v))}{|E(G)|}\).
Each path \(P_i\) joining \(v_i\) to \(\pi (v_i)\) has at least \(d(v_i,\pi (v_i))\) edges, so the total edge usage is \(\sum _e rc(e,G,\pi ,P)=\sum _i|P_i|\ge \sum _v d(v,\pi (v))\). Averaging over the \(|E(G)|\) edges, the maximum usage is at least \(\sum _v d(v,\pi (v))/|E(G)|\).
For the \(n\)-cube \(Q_n\), \(rc(Q_n)\le 4\).
For the \(n\)-cube \(Q_n\), \(rc(Q_n)\ge 2\).
Take \(\pi \) to be the antipodal map, so \(d(v,\pi (v))=n\) for all \(v\). Then \(\sum _v d(v,\pi (v))=n\cdot 2^{n}\) while \(|E(Q_n)|=n\, 2^{n-1}\), and Lemma 163 gives \(rc(Q_n)\ge n2^{n}/(n2^{n-1})=2\).
Let \(G\) and \(G'\) be connected regular graphs with the same vertex set, eigenvalues \(\lambda _1,\lambda _1'\) and degrees \(k,k'\) respectively. Assume that for each edge \(\{ x,y\} \in E(G)\) there is a path \(P(x,y)\) in \(G'\) joining \(x\) and \(y\) of length at most \(l\), and that every edge of \(G'\) lies in at most \(m\) of the paths \(P(x,y)\). Then
Let \(f\) be the harmonic eigenfunction achieving \(\lambda _1'\) in \(G'\), with \(\sum _x f(x)=0\). Then
The last factor is \(\ge \lambda _1\) by the variational principle in \(G\). For \(\{ x,y\} \in E(G)\) and its path \(P(x,y)\) in \(G'\), Lemma 137 gives \((f(x)-f(y))^2\le l\sum _{e\in P(x,y)}f^2(e)\) with \(f^2(e)=(f(a)-f(b))^2\). Since each edge of \(G'\) lies in at most \(m\) paths,
so \(\dfrac {\sum _{\{ x,y\} \in E(G')}(f(x)-f(y))^2}{\sum _{\{ x,y\} \in E(G)}(f(x)-f(y))^2}=\dfrac {\sum _{e\in E(G')}f^2(e)}{\sum _{\{ x,y\} \in E(G)}(f(x)-f(y))^2}\ge \dfrac {1}{lm}\). Combining, \(\lambda _1'\ge \dfrac {k}{k’}\cdot \dfrac {1}{lm}\cdot \lambda _1=\dfrac {k\lambda _1}{k’lm}\).
Let \(G\) and \(G'\) be connected graphs with the same vertex set and eigenvalues \(\lambda _1,\lambda _1'\). Assume that for each edge \(\{ x,y\} \in E(G)\) there is a path \(P(x,y)\) in \(G'\) of length at most \(l\), that for each vertex \(v\) the degree \(d_v\) of \(v\) in \(G\) satisfies \(d_v\ge a\, d_v'\) (with \(d_v'\) its degree in \(G'\)), and that every edge of \(G'\) lies in at most \(m\) paths \(P(x,y)\). Then
This is the special case of Theorem 168 in which the embedding \(\varphi \colon V(G)\to V(G')\) is the identity: then \(\varphi ^{-1}(v)=\{ v\} \), so condition (b) \(\sum _{x\in \varphi ^{-1}(v)}d_x\ge a\, d_v'\) becomes \(d_v\ge a\, d_v'\), and conditions (a),(c) are the path and congestion hypotheses. The conclusion \(\lambda _1'\ge a\lambda _1/(lm)\) follows.
Let \(G\) and \(G'\) be connected graphs with eigenvalues \(\lambda _1,\lambda _1'\), and suppose \(V(G)\) is embedded into \(V(G')\) by a map \(\varphi \colon V(G)\to V(G')\). Suppose that for fixed positive \(a,l,m\):
each edge \(\{ x,y\} \in E(G)\) is associated with a path \(P_{x,y}\) joining \(\varphi (x)\) to \(\varphi (y)\) in \(G'\) of length at most \(l\);
for each \(v\in V(G')\), \(\displaystyle \sum _{x\in \varphi ^{-1}(v)}d_x\ge a\, d_v'\) (with \(d_x,d_v'\) the degrees in \(G,G'\));
each edge of \(G'\) lies in at most \(m\) of the paths \(P_{x,y}\).
Then \(\displaystyle \lambda _1'\ge \frac{a\lambda _1}{lm}\).
Let \(g\) be the harmonic eigenfunction of \(G'\) achieving \(\lambda _1'\), so \(\sum _{v}g(v)d_v'=0\) and \(\lambda _1'=\dfrac {\sum _{\{ u,v\} \in E(G')}(g(u)-g(v))^2}{\sum _v g^2(v)d_v’}\). Define \(f\colon V(G)\to \mathbb {R}\) by \(f(x)=g(\varphi (x))-c\), with \(c\) chosen so that \(\sum _x f(x)d_x=0\).
Step 1 (vertex sums). Grouping vertices of \(G\) by their image and using (b),
the last step because \(\sum _v(g(v)-c)^2d_v'=\sum _v g^2(v)d_v'+c^2\operatorname {vol}G'\ge \sum _v g^2(v)d_v'\), using \(\sum _v g(v)d_v'=0\).
Step 2 (edge sums). For \(\{ x,y\} \in E(G)\) with \(u=\varphi (x),v=\varphi (y)\), since \(f(x)-f(y)=g(u)-g(v)\), Lemma 137 applied to the path \(P_{x,y}\) gives \((g(u)-g(v))^2\le l\sum _{e\in P_{x,y}}g^2(e)\), with \(g^2(e)=(g(a)-g(b))^2\). Summing and using (c),
i.e. \(\displaystyle \sum _{\{ u,v\} \in E(G')}(g(u)-g(v))^2\ge \frac{1}{ml}\sum _{\{ x,y\} \in E(G)}(f(x)-f(y))^2\).
Step 3 (combine). Using the Rayleigh bound \(\sum _{\{ x,y\} \in E(G)}(f(x)-f(y))^2\ge \lambda _1\sum _x f^2(x)d_x\) (valid since \(\sum _x f(x)d_x=0\)) and then Step 1,
Dividing by \(\sum _v g^2(v)d_v'\) gives \(\lambda _1'\ge \dfrac {a\lambda _1}{ml}\).
Theorems 140 and 142 are the special cases of Theorem 168 in which \(G\) is a complete graph and \(G'\) is arbitrary.
Let \(H\) be a graph on \(n\) vertices, each labelled by an element of a finite group \(\Gamma \), and consider the walk in which at each step one vertex \(v\) with label \(f\) may be relabelled \(gf\) or \(f^{-1}\), where \(g\) is the label of a neighbor of \(v\); assume the initial labels generate \(\Gamma \). Then, using Theorem 168, the mixing time toward a random generating set is at most \(c\, D\, n^{2}\), where \(c\) depends only on \(|\Gamma |\) and \(D\) is the diameter of \(H\).