# Expansion Lemma--Variations and Applications to Polynomial-Time Preprocessing
## 2 Preliminaries
### Sets, Numbers, and Graph Theory  
We use \(\mathbb{N}\) to denote the set of natural numbers. For \(r\in\mathbb{N}\), we denote the set \(\{1,\ldots,r\}\) by \([r]\). A _Boolean formula_ is an expression of binary variables with a logical operator conjunction (\(\wedge\)), disjunction (\(\vee\)), and negation (\(\
eg\)). A Boolean formula is in _conjunctive normal form_ (or _CNF_) if it is a conjunction of clauses. A _literal_ is a Boolean variable in its own form or in its complemented form. Each clause is a disjunction of literal. We usually use \(G=(V,E)\) to denote an undirected graph, and \(D=(V,A)\) to denote a directed graph. Let \(V(G)\) denote the set of vertices of \(G\), and \(E(G)\) the set of edges of \(G\). When \(G\) is clear from context, let \(n=|V(G)|\) and \(m=|E(G)|\). Informally, we use \(n\) to denote the number of vertices and \(m\) to denote the number of edges in the input graph. Given a graph \(G=(V,E)\) and \(X\subseteq V(G)\), we use \(G[X]\) to denote an _induced subgraph_ of \(G\); its vertex set is \(X\), and its edge set consists of all edges of \(E(G)\) that have both endpoints in \(X\). Let \(G-X\) denote the subgraph of \(G\) induced on the vertex set \(V(G)\setminus X\). A _clique_ in an undirected graph is a set of vertices where every pair of vertices are adjacent to each other. An _independent set_ is a pairwise non-adjacent set of vertices. A _tournament_ is a directed graph \(T\), such that for every pair of vertices \(u,v\in V(T)\), one of \(uv\) or \(vu\) is a directed edge of \(T\). In an undirected graph \(G=(V,E)\), a _path_ is a set \(P\) of distinct vertices (except possibly for the start vertex and the end vertex), such that the vertices of \(P\) can be arranged in an order \(v_{1},\ldots,v_{d}\), such that for every \(1\leq i\leq d-1\), \(v_{i}v_{i+1}\in E(G)\). Informally, for all \(1\leq i\leq d-1\), \(v_{i}\
eq v_{i-1}\) for a path. Similarly, in a directed graph \(D=(V,A)\), a _directed path_ can be defined in a similar way when for every \(i\leq d-1\), \((v_{i},v_{i+1})\in A\). A (directed) _cycle_ is a (directed) path that starts and ends at the same vertex. A _connected component_ of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. For subsets \(X,A,B\subseteq V(G)\), we say \(X\)_separates_\(A\) and \(B\) when no component of \(G-X\) contains vertices from both \(A\setminus X\) and \(B\setminus X\). Given a vertex subset \(X\subseteq V(G)\), we use \(N_{G}(X)\) to denote the _open neighborhood_ of \(X\) and \(N_{G}[X]\) to denote the _closed neighborhood_ of \(X\). When graph \(G\) is clear from the context, we omit the subscript. A vertex \(v\) of \(G\) is a _cut vertex_ if \(G-\{v\}\) has more connected components than \(G\). Graph \(G\) is _bi-connected_ if \(|V(G)\geq 3\), and it has no cut vertex. Graph \(G\) is a _block graph_ if each of its maximal bi-connected components is a clique. A _tree_ is a connected undirected graph with no cycle (or equivalently, a connected undirected acyclic graph). A _forest_ is a graph, every connected component of which is a tree. A _directed acyclic graph_ is a directed graph with no directed cycles. A _topological ordering_ for a directed acyclic graph is a linear ordering of vertices, such that for every directed edge \(uv\), vertex \(u\) comes before \(v\) in the ordering. An undirected graph \(G=(V,E)\) is said to be _bipartite_ if \(V(G)=A\uplus B\), such that for every \(uv\in E(G)\), \(u\in A\) if and only if \(v\in B\). We call \(A\) and \(B\) the bipartitions of \(G\). Another alternate characterization is that a bipartite graph has no odd cycle. We use \(G=(A\uplus B,E)\) to denote a bipartite graph such that \(A\) and \(B\) are its bipartitions and \(E\) is the set of its edges. A set \(M\subseteq E(G)\) is said to be a _matching_ of a graph if for every two edges \(uv,xy\in M\), \(\{u,v\}\cap\{x,y\}=\emptyset\). A vertex \(u\in V(G)\) is said to be _matched_ by a matching \(M\), if there is an edge of \(M\) incident on \(u\).