= Solution
Under the standard intended reading that the added edges form a <perfect matching> between $G_n$ and $H_n$, the claim follows as follows. Degrees in $M_n$ remain bounded in terms of $\Delta$. For $A\subseteq V(M_n)$, write $A_G=A\cap V(G_n)$ and $A_H=A\cap V(H_n)$. The matching contributes at least $\bigl||A_G|-|A_H|\bigr|$ boundary edges, while expansion inside $G_n$ contributes a constant multiple of $\min\{|A_G|,n-|A_G|\}$. A case split according as $|A_G|\leq n/2$ or $|A_G|>n/2$ shows
$$
|\partial_{M_n}A|\geq c_{\alpha,\Delta}
\min\{|A|,2n-|A|\}.
$$
Thus $M_n$ has a uniform <Cheeger constant>. <Cheeger inequality> gives a uniformly bounded relaxation time, while $\pi_{\min}\asymp1/n$. The usual spectral mixing estimate, or part (b), then gives $t_{\mathrm{mix}}\lesssim\log n$.
If “adding $n$ edges” permits all $G_n$ vertices to attach to the same vertex of $H_n$, the assertion is false as written. Take $H_n$ to be a path and attach every vertex of the expander to one endpoint. A walk started at the other endpoint needs order $n^2$ time to reach the attachment endpoint, so its mixing time is not $O(\log n)$. The perfect-matching interpretation is therefore necessary.
Solved by gpt-5.6-sol high.
Back to article page
