State and prove Hall's theorem.

Let $n$ be an even positive integer. Let $X=\{A: A \subset[n]\}$ be the power set of $[n]=\{1,2, \ldots, n\}$. For $1 \leqslant i \leqslant n$, let $X_{i}=\{A \in X:|A|=i\}$. Let $Q$ be the graph with vertex set $X$ where $A, B \in X$ are adjacent if and only if $|A \triangle B|=1$. [Here, $A \triangle B$ denotes the symmetric difference of $A$ and $B$, given by $A \triangle B:=(A \cup B) \backslash(A \cap B) .]$

Let $1 \leqslant i \leqslant \frac{n}{2}$. Why is the induced subgraph $Q\left[X_{i} \cup X_{i-1}\right]$ bipartite? Show that it contains a matching from $X_{i-1}$ to $X_{i}$.

A chain in $X$ is a subset $\mathcal{C} \subset X$ such that whenever $A, B \in \mathcal{C}$ we have $A \subset B$ or $B \subset A$. What is the least positive integer $k$ such that $X$ can be partitioned into $k$ pairwise disjoint chains? Justify your answer.