Induced Subgraphs and Hereditary Graph Classes — Examples

By deleting one triangle edge, $K_3$ contains an ordinary subgraph copy of $P_3$.

Any injection from the three vertices of $P_3$ to the three vertices of $K_3$ is bijective, but the two endpoints of $P_3$ are nonadjacent while their images in $K_3$ are adjacent.

Thus $K_3$ contains no induced $P_3$, despite containing an ordinary subgraph copy.

An induced embedding of $K_2$ is exactly an ordered adjacent pair $(u,v)$ of vertices of $G$.

Counting ordered adjacent pairs by their first vertex gives $\sum_{u\in V(G)}\deg(u)$.

By the handshake lemma this is $2|E(G)|$, proving the formula.

The class $\mathcal K$ is isomorphism-closed and closed under induced subgraphs, so it is hereditary.

The graph $\overline K_2$ is not complete, while each of its proper induced subgraphs is $K_0$ or $K_1$ and is complete. Thus it is minimally forbidden.

Every noncomplete graph has two nonadjacent vertices, and they induce $\overline K_2$. Hence avoiding $\overline K_2$ is equivalent to being complete.

Therefore $\{\overline K_2\}$ is the unique minimal forbidden basis of $\mathcal K$.

The class $\mathcal E$ is the complement class of the complete graphs.

Therefore it is hereditary and its basis is obtained by complementing $\overline K_2$.

That complement is $K_2$, so the basis is $\{K_2\}$.

If every component is complete, three vertices in one component induce all three edges, while vertices meeting more than one component induce edges only within their component parts and therefore at most one edge. Neither pattern is $P_3$, so $G$ is $P_3$-free.

Conversely, suppose a component contains nonadjacent vertices $x,y$. Choose a shortest $x$-$y$ path $x=v_0,v_1,\ldots,v_k=y$, where $k\ge2$.

Minimality of the path gives $v_0v_2\notin E(G)$, so $G[\{v_0,v_1,v_2\}]\cong P_3$.

Therefore a $P_3$-free graph cannot have a noncomplete component. Combining both directions proves the equivalence.

The graph $P_3$ belongs to the class of connected graphs.

Its induced subgraph on the endpoints is $\overline K_2$, which is disconnected.

Hence this class is not closed under induced subgraphs and is not hereditary.

The graph $C_4$ is regular.

Its displayed induced $P_3$ has degrees $1,2,1$, so it is not regular.

Thus regular graphs are not closed under induced subgraphs and do not form a hereditary class.

The graph $P_4$ is connected.

Its complement has edges $13,14,24$, which form the path $3,1,4,2$. Thus $\overline{P_4}\cong P_4$ and is connected.

Therefore $P_4$ is anticonnected as well as connected.

Both $21$ and $23$ are edges, so $(\{2\},\{1,3\})$ is complete.

Neither $13$ nor $14$ is an edge, so $(\{1\},\{3,4\})$ is anticomplete.

The pair $23$ is an edge but $24$ is not, so $(\{2\},\{3,4\})$ is mixed.

These verify the three claimed pair types.

Suppose the minimal forbidden basis of $\mathcal B$ is finite.

For every $k\ge1$, the graph $C_{2k+1}$ is not bipartite. Every proper induced subgraph of this chordless cycle is a disjoint union of paths, hence is bipartite. Thus $C_{2k+1}$ is minimally forbidden.

The minimal basis therefore contains the pairwise nonisomorphic graphs $C_3,C_5,C_7,\ldots$.

This is an infinite family, contradicting step 1.1. Hence a hereditary class need not have a finite minimal forbidden basis.

The graph $K_3$ belongs to $\mathcal K$.

Deleting one edge gives an ordinary subgraph $P_3$, which is not complete and hence does not belong to $\mathcal K$.

Therefore the hereditary class $\mathcal K$ is not closed under arbitrary subgraphs.

Complementing a complete graph gives an edgeless graph and vice versa, so $\mathcal E=\overline{\mathcal K}$.

The two basis graphs satisfy $\overline{\overline K_2}=K_2$.

Thus the displayed bases are complementary, exactly as the general theorem predicts.