28 Cor 1: Alon–Chung Contrapositive
Let \(E \subseteq X_1\) be a set of edges in a simple graph \(G\) on vertex type \(V\). The set of vertices incident to \(E\) is defined as
That is, \(\Gamma (E)\) consists of all vertices that appear as an endpoint of some edge in \(E\).
For any edge set \(E\) and vertex \(v\),
This holds by unfolding the definition of \(\Gamma (E)\) and simplifying.
If \(E\) is a set of edges such that some edge in \(E\) has a vertex, then \(\Gamma (E)\) is nonempty.
Suppose there exists \(e \in E\) and \(v \in e\). We obtain \(e\), \(v\), and the membership proof. By the membership characterization of \(\Gamma (E)\), \(v \in \Gamma (E)\), so \(\Gamma (E)\) is nonempty.
Let \(G\) be a simple graph and \(E \subseteq \operatorname {edgeFinset}(G)\). Then
Let \(e \in E\) be arbitrary. We must show \(e \in \operatorname {inducedEdges}(G, \Gamma (E))\). Rewriting via the membership criterion for \(\operatorname {inducedEdges}\), we need: (1) \(e \in \operatorname {edgeFinset}(G)\), which holds since \(e \in E \subseteq \operatorname {edgeFinset}(G)\); and (2) every vertex \(v \in e\) lies in \(\Gamma (E)\). For any such \(v\), rewriting via the membership criterion for \(\Gamma (E)\), we exhibit \(e \in E\) and \(v \in e\), establishing \(v \in \Gamma (E)\).
Let \(c \in \mathbb {R}\) with \(0 \leq c \leq 1\), and let \(0 \leq a \leq b\). Then
Define \(f(t) = t^2 + c \cdot t(1-t) = (1-c)t^2 + ct\). Then
Since \(b \geq a \geq 0\) and \(0 \leq c \leq 1\), we have \(b - a \geq 0\), \((1-c) \geq 0\), \(b + a \geq 0\), and \(c \geq 0\), so \((b-a)[(1-c)(b+a)+c] \geq 0\). This is verified by nonlinear arithmetic using \(a^2 \geq 0\), \(b^2 \geq 0\), \((b-a)^2 \geq 0\), and the nonnegativity of \((b-a)\cdot [(1-c)(b+a)+c]\).
Let \(G\) be a \(s\)-regular simple graph on \(V\) with \(|V| \geq 2\) and \(s \geq 1\). Let \(\lambda _2\) denote the second-largest adjacency eigenvalue of \(G\) with \(\lambda _2 \geq 0\). Let \(E \subseteq \operatorname {edgeFinset}(G)\) and \(0 {\lt} \gamma {\lt} 1\). If
then
Let \(S = \Gamma (E)\). We consider two cases.
Case 1: \(S = \emptyset \). We claim \(E = \emptyset \). Indeed, suppose for contradiction that \(E\) is nonempty; pick \(e \in E\). Since \(e \in \operatorname {edgeFinset}(G)\), writing \(e = s(v,w)\) via the induction principle for \(\operatorname {Sym2}\), we have \(v \in S\) by definition of \(\Gamma (E)\) (since \(v \in e \in E\)), contradicting \(S = \emptyset \). Thus \(|E| = 0 \leq \alpha \cdot |\operatorname {edgeFinset}(G)|\), where \(\alpha = \gamma ^2 + (\lambda _2/s)\gamma (1-\gamma ) \geq 0\) (since \(\lambda _2/s \geq 0\), \(\gamma {\gt} 0\), and \(1 - \gamma {\gt} 0\), this follows by nonlinear arithmetic).
Case 2: \(S \neq \emptyset \). Set \(n = |V|\) and \(\gamma ' = |S|/n\). Then \(\gamma ' {\gt} 0\) (since \(S\) is nonempty and \(n {\gt} 0\)) and \(\gamma ' \leq \gamma \) (from the hypothesis \(|S| \leq \gamma n\)). Moreover, \(|S| {\lt} |V|\): if \(|S| \geq |V|\), then \(|V| \leq |S| \leq \gamma |V|\), giving \(1 \leq \gamma \), contradicting \(\gamma {\lt} 1\).
By Lemma 326, \(E \subseteq \operatorname {inducedEdges}(G, S)\), so \(|E| \leq |\operatorname {inducedEdges}(G,S)|\).
Applying the Alon–Chung theorem (Theorem 322) to \(S\):
where \(\alpha ' = {\gamma ’}^2 + (\lambda _2/s)\, \gamma '(1-\gamma ')\).
We verify \(\lambda _2/s \leq 1\): by Lemma 316, the largest eigenvalue equals \(s\), and by antitonicity of adjacency eigenvalues (Theorem 241), \(\lambda _2 \leq s\), so \(\lambda _2/s \leq 1\).
By Lemma 327 applied with \(c = \lambda _2/s \in [0,1]\) and \(0 {\lt} \gamma ' \leq \gamma \), we obtain \(\alpha ' \leq \alpha = \gamma ^2 + (\lambda _2/s)\gamma (1-\gamma )\).
Combining via a calculation:
where the last step uses \(\alpha ' \leq \alpha \) and \(|\operatorname {edgeFinset}(G)| \geq 0\).
Let \(G\) be a \(s\)-regular simple graph on \(V\) with \(|V| \geq 2\) and \(s \geq 1\). Let \(\lambda _2 \geq 0\) be the second-largest adjacency eigenvalue. Let \(E \subseteq \operatorname {edgeFinset}(G)\) and \(0 {\lt} \gamma {\lt} 1\). Set \(\alpha = \gamma ^2 + \tfrac {\lambda _2}{s}\, \gamma (1-\gamma )\). If
then
In other words, if \(E\) is a large fraction of edges, then \(E\) is incident to many vertices.
We argue by contradiction. Suppose \(|\Gamma (E)| \leq \gamma \cdot |V|\). Then by Theorem 328, we have \(|E| \leq \alpha \cdot |\operatorname {edgeFinset}(G)|\). This contradicts the hypothesis \(|E| {\gt} \alpha \cdot |\operatorname {edgeFinset}(G)|\), so by linear arithmetic we obtain a contradiction. Therefore \(|\Gamma (E)| {\gt} \gamma \cdot |V|\).