Gallai's modular decomposition theorem: a graph on at least two vertices is disconnected, or has a disconnected complement, or has a modular partition into its maximal proper modules whose quotient is prime

By [L3] the graph is connected or anticonnected, so it is not the case that both $G$ and $\bar{G}$ are disconnected; the three listed situations are therefore mutually exclusive, and they are exhaustive because $G$ is disconnected, or $\bar{G}$ is disconnected, or both are connected.

First case: $G$ is disconnected. By [L5] the vertex sets of its components are nonempty, pairwise disjoint and cover $V(G)$, and by [L2] each is a module, so they form a modular partition $\mathcal{P}$.

Second case: $\bar{G}$ is disconnected, that is, $G$ is not anticonnected. By [L6] the anticomponents are nonempty, pairwise disjoint and cover $V(G)$, and by [L2] each is a module, so they form a modular partition $\mathcal{Q}$.

Third case: $G$ and $\bar{G}$ are both connected, so $G$ is connected and anticonnected. By [L1] the sets $M(v)$ are proper modules, pairwise equal or disjoint, and cover $V(G)$; they are nonempty since $v\in M(v)$, so the distinct ones form a modular partition $\mathcal{R}$.

In the first case, distinct components are anticomplete to one another by [L7], so no pair of distinct parts of $\mathcal{P}$ is complete and the quotient $G\mathrm{/}\mathcal{P}$ has no edge.

In the second case, distinct anticomponents are complete to one another by [L7], so every pair of distinct parts of $\mathcal{Q}$ is complete and every pair of distinct vertices of $G\mathrm{/}\mathcal{Q}$ is an edge.

In the third case $\mathcal{R}$ has at least two parts: a single part would be $M(v)=V(G)$ for some $v$, contradicting that $M(v)$ is proper.

Still in the third case, let $\mathcal{X}$ be a module of $G\mathrm{/}\mathcal{R}$ that is neither $\mathrm{\varnothing }$ nor $\mathcal{R}$, and put $U={\bigcup }_{M\in \mathcal{X}}M$. By [L4] the set $U$ is a module of $G$, and $U\mathrm{\ne }V(G)$ because some part outside $\mathcal{X}$ is nonempty and disjoint from $U$, so $U$ is a proper module.

Choose $M\in \mathcal{X}$, possible because $\mathcal{X}\mathrm{\ne }\mathrm{\varnothing }$, and $x\in M$, possible because parts are nonempty. Then $M=M(u)$ for some $u$, and $M(x)$ meets $M(u)$ at $x$, so $M(x)=M$ by [L1]; the set $U$ is a proper module containing $x$, so maximality gives $U\subseteq M(x)=M$. Every $M^{\mathrm{\prime }}\in \mathcal{X}$ therefore satisfies $M^{\mathrm{\prime }}\subseteq M$, and a part distinct from $M$ is disjoint from $M$ and nonempty, so no such part lies in $\mathcal{X}$: that is, $\mathcal{X}=\{M\}$.

So in the third case every module of $G\mathrm{/}\mathcal{R}$ is $\mathrm{\varnothing }$, a singleton or all of $\mathcal{R}$, that is, $G\mathrm{/}\mathcal{R}$ is prime; with steps 1.1, 2.1, 2.2 and 2.3 this proves all three clauses and their mutual exclusion.