Modules, Substitution and Prime Graphs — Examples

In $K_n$, every vertex outside $M$ is adjacent to every member of $M$, so [L1] makes $M$ a module.

In $\overline{K_n}$, every vertex outside $M$ is adjacent to no member of $M$, so [L1] again makes $M$ a module.

If $n\ge 3$, then $K_n$ and $\overline{K_n}$ have nontrivial modules by steps 1.1 and 1.2, so [L3] shows that neither is prime. For $n=1$ and $n=2$ there is no subset of size between $2$ and $n-1$, so every module is trivial and both graphs are prime.

Each two-element subset is split by an outside vertex: $2$ splits $\{0,1\}$, $3$ splits $\{0,2\}$, $1$ splits $\{0,3\}$, $3$ splits $\{1,2\}$, $0$ splits $\{1,3\}$, and $1$ splits $\{2,3\}$. So no two-element subset is a module by [L1].

Each three-element subset is split by its remaining vertex: $3$ splits $\{0,1,2\}$, $2$ splits $\{0,1,3\}$, $1$ splits $\{0,2,3\}$, and $0$ splits $\{1,2,3\}$. So no three-element subset is a module.

The only modules left are $\mathrm{\varnothing }$, the singletons, and the whole vertex set, so [L2] makes $P_4$ prime.

If $G$ is prime, then $G$ is connected and anticonnected. Indeed, if $G$ were disconnected, some union of connected components would have size $2$ or $3$; by [L1] that union would be a nontrivial module, contradicting [L2]. The same argument in $\bar{G}$ shows that if $\bar{G}$ were disconnected, a union of anticomponents of $G$ would be a nontrivial module.

Let $G$ be connected and anticonnected. No vertex has degree $0$, since $G$ is connected, and no vertex has degree $3$, since such a vertex is isolated in $\bar{G}$. Thus every vertex has degree $1$ or $2$.

Some vertex has degree $1$. Otherwise every vertex has degree $2$; following neighbours from any vertex then forces the four vertices to form $C_4$, whose complement is the disjoint union of two edges, contrary to anticonnectedness.

Let $v_0$ have unique neighbour $v_1$. Connectivity gives $v_1$ a neighbour $v_2\mathrm{\ne }{v}_0$, and connectivity of the remaining vertex $v_3$ forces an edge from $v_3$ to $v_1$ or $v_2$. The edge $v_1{v}_3$ is impossible, since then $v_1$ has degree $3$; hence $v_2{v}_3$ is an edge. There are no further edges: $v_0$ has degree $1$, $v_1{v}_3$ was excluded, and $v_2$ already has the two neighbours $v_1,v_3$. Therefore $G$ is the path $v_0{v}_1{v}_2{v}_3$.

Every prime graph on four vertices is therefore isomorphic to $P_4$, and [L3] shows that $P_4$ is prime.

Suppose, for contradiction, that $P_n$ has a nontrivial module $M$. Then $M$ is a nonempty proper module, so [L2] gives a vertex $v\mathrm{\notin }M$ complete to $M$.

Since $v$ is complete to $M$ in a path, [L3] forces $v$ to be an interior vertex and $M$ to be exactly the two neighbours of $v$.

One of the vertices at distance two from $v$ exists because $n\ge 4$, and it is adjacent to exactly one of the two neighbours of $v$. That vertex therefore splits $M$, contradicting that $M$ is a module.

No nontrivial module exists, so [L1] makes $P_n$ prime.

Suppose, for contradiction, that $C_5$ has a nontrivial module $M$. Then [L2] gives a vertex $v\mathrm{\notin }M$ complete to $M$.

By [L3], the set $M$ must be the two neighbours of $v$.

The two remaining vertices of the cycle each see exactly one of those neighbours, so they split $M$, contradicting that $M$ is a module.

Therefore $C_5$ has no nontrivial module, and [L1] makes it prime.

First substitute $G_1$ for $x$, leaving $y$ as a one-vertex part, and then substitute $G_2$ for $y$. Since $x$ and $y$ are adjacent in $K_2$, [L1] makes every vertex of $G_1$ adjacent to every vertex of $G_2$, while preserving the edges internal to both graphs. The result is exactly $G_1\vee G_2$.

Carrying out the same two substitutions in $\overline{K_2}$ leaves the two copied vertex sets anticomplete because $x$ and $y$ are nonadjacent. The result is exactly $G_1\bigsqcup G_2$.

Thus join and disjoint union are the two binary substitutions obtained from the edge and the nonedge templates.

Each blown-up copy of $\overline{K_t}$ is a module of $G$: every vertex outside one part lies in another part, and that whole outside part is either complete or anticomplete to the chosen part according to the corresponding adjacency in the five-cycle. Hence every outside vertex is complete or anticomplete to the chosen part, so [L1] applies.

The graph $G$ is connected: paths between blown-up parts lift from paths in $C_5$, and two vertices in one edgeless part have a common neighbour in either adjacent part. Its complement is connected by the same argument, because complementation turns the quotient into $\overline{C_5}\cong C_5$ and each blown-up part into a clique. Thus $G$ is connected and anticonnected.

The quotient obtained by collapsing those five modules is the original five-cycle, so [L2] shows that this quotient is prime.

The five blown-up parts form a modular partition with at least two parts and prime quotient $C_5$ by steps 1.1 and 2.1. Hence [L3] and step 1.2 show that they are exactly the maximal proper modules, and the quotient graph is $C_5$.

Exactly the vertex sets $\{0,1,2\}$ and $\{1,2,3\}$ induce a copy of $P_3$ inside $P_4$.

Each of those two vertex sets supports two induced embeddings of $P_3$, one for each automorphism of the path, so [L1] gives ${\mathrm{ind}}_{P_3}(P_4)=4$.

Delete the endpoint labelled $0$ from the pattern $0$-$1$-$2$. The six oriented edge embeddings $1\mapsto a,2\mapsto b$ in $P_4$ have extension-set sizes $0,1,1,1,1,0$ for $(a,b)=(0,1),(1,0),(1,2),(2,1),(2,3),(3,2)$ respectively: the extending image of $0$ must be adjacent to $a$ and nonadjacent to $b$. Their sum is $4$, agreeing with step 2.1 and [L2].

By [L1], both $P_3$ and $K_2$ have the Erdős–Hajnal property.

The substitution identifies one endpoint of $P_3$ with an edge, so the result is a triangle with one pendant edge, that is, the paw graph.

Applying [L2] to the two factors from step 1.1 gives the Erdős–Hajnal property for the paw.

The sets $M=\{0\}$ and $N=\{2\}$ are disjoint.

By [L1], both $M$ and $N$ are modules of $P_4$.

The vertex $3$ lies outside $M\cup N$, is adjacent to $2$, and is not adjacent to $0$ by [L2], so it splits $M\cup N$. Hence $M\cup N$ is not a module.

Thus $P_4$ with $M$ and $N$ is a counterexample to the claim.

The set $N=\{a,b\}$ is a module: the only outside vertices are $c$ and $d$, and $c$ is complete to $N$ while $d$ is anticomplete to $N$.

The set $M$ is the whole vertex set, so it is a module vacuously.

The difference $M\setminus N=\{c,d\}$ is not a module, because the vertex $a$ is adjacent to $c$ and not to $d$.

Here $N\subseteq M$, so the two modules do not overlap. Thus the overlap hypothesis in [L2] cannot be weakened to inclusion.

In the edgeless graph $E_3$, every subset is a module, because every outside vertex is anticomplete to it.

The sets $\{a,b\}$ and $\{a,c\}$ are proper modules, and each is maximal among proper modules because the only larger module containing it is the whole vertex set.

These two maximal proper modules meet in $a$, so they are not pairwise disjoint.

By [L3], the same two sets are also overlapping maximal proper modules in the complement graph $K_3$, which is connected while its complement is disconnected.

Therefore the conclusion of [L2] genuinely needs the connected-and-anticonnected hypotheses.

By [L1], the graph $P_5$ is prime.

Deleting the middle vertex $2$ leaves the induced subgraph on $\{0,1,3,4\}$, which is the disjoint union of the two edges $01$ and $34$.

In that four-vertex induced subgraph, the set $\{0,1\}$ is a proper module of size two, since every outside vertex is anticomplete to it. So [L2] shows that the induced subgraph is not prime.

Hence a prime graph can have an induced subgraph that is not prime.

The claim asserts that every graph with at least four vertices has some module that is neither empty, nor a singleton, nor the whole vertex set.

The graph $P_4$ has four vertices and, by [L1], has no such module.

So the claim is false. Equivalently, [L2] shows that $P_4$ is a prime graph on four vertices.