Subgraphs and Special Graph Families

In graph coloring, the chromatic number of $G$ and the clique number $\omega(G)$ (the largest $n$ with $K_n$ as an induced subgraph) are linked by $\chi(G) \ge \omega(G)$, and perfect graphs are exactly those where this bound is tight for every induced subgraph — a definition that could not even be stated without the induced-subgraph concept. This sets up the transition to Graph Coloring and Chromatic Number. In Ramsey theory, the complement operation is the engine of the argument: Ramsey's theorem guarantees that for large enough $n$, any red/blue coloring of the edges of $K_n$ contains a monochromatic $K_k$, and phrasing "red edges" as $G$ and "blue edges" as $\overline{G}$ is the standard setup, directly using Edge complementarity. In bipartite structure detection, checking whether a graph contains an odd cycle $C_{2k+1}$ as a subgraph is the combinatorial heart of testing bipartiteness, foreshadowing Bipartite Graphs and Characterization. In computer science, induced subgraph isomorphism (deciding whether $G[S] \cong H$ for some $S$) is NP-complete in general and underlies pattern-matching in chemical structure search, social network motif detection, and database query graphs. Paths and cycles as subgraphs are the basic objects tested by depth-first search (for cycle detection) and by shortest-path algorithms (which return induced or non-induced paths depending on the algorithm). In statistics and network science, complements of "similarity graphs" (where edges mean "similar") give "dissimilarity graphs," and clique-finding in one is independent-set-finding in the other, a direct application of the clique/independent-set duality from Example 2. In coding theory and design theory, complete graphs $K_n$ model round-robin tournament schedules, and their edge decompositions into paths or cycles (Hamiltonian decomposition of $K_n$) are classical combinatorial design problems.

Ask the tutor: Can you show why every self-complementary graph must have $4$ or $4k{+}1$ vertices, with a full worked construction for $n=5$?

Think of $G$ as a friendship network drawn on a fixed set of people. A subgraph corresponds to choosing some people and some of their real friendships to record — perhaps you only wrote down half the friendships you know about among the people you chose. An induced subgraph is stricter: once you decide which people to include, you must record every friendship that actually exists among them. This is why induced subgraphs are so natural for questions like "is there a clique of size $4$ hiding in here?" — a clique is a set of vertices whose induced subgraph is complete, and the answer would be corrupted if we were allowed to selectively drop edges. The complement flips the entire picture: $\overline{G}$ records exactly the non-friendships. A set of vertices that forms a clique in $G$ becomes an independent set (no edges at all) in $\overline{G}$, and vice versa. This duality is why the complement operation is indispensable in coloring theory and Ramsey theory: statements about cliques in $G$ translate directly into statements about independent sets in $\overline{G}$.

:::svg[$G$ on 5 vertices, an induced subgraph $G[\{1,2,3,4\}]$, and a non-induced subgraph on the same vertex set]

The corollary follows because $\overline{E}$ is defined as $\binom{V}{2}\setminus E$, and taking complements twice removes the same set twice: $\binom{V}{2} \setminus (\binom{V}{2}\setminus E) = E$, using the set-theoretic identity $A \setminus (A \setminus B) = B$ for $B \subseteq A$ (here $B = E \subseteq \binom{V}{2} = A$).

Example 1: Petersen-style asymmetric example on 6 vertices. Let $V = \{1,2,3,4,5,6\}$ and let $G$ have edge set

So $G$ is a $6$-cycle $1$–$2$–$3$–$4$–$5$–$6$–$1$ with one extra "diagonal" chord $\{1,4\}$, giving $|E| = 7$ edges. Subgraph vs. induced subgraph. Take $S = \{1,2,3,4\}$.

• The induced subgraph $G[S]$ must contain every edge of $G$ with both endpoints in $S$. Scanning $E$: $\{1,2\}\subseteq S$ (yes), $\{2,3\}\subseteq S$ (yes), $\{3,4\}\subseteq S$ (yes), $\{4,5\}$ (no, $5\notin S$), $\{5,6\}$ (no), $\{1,6\}$ (no), $\{1,4\}\subseteq S$ (yes). So

a $4$-cycle $C_4$ on $\{1,2,3,4\}$ — four edges.

• A non-induced subgraph $H$ on the same vertex set $S$ could legally omit some of these, e.g. $H$ with $V(H) = \{1,2,3,4\}$ and $E(H) = \{\{1,2\},\{3,4\}\}$ is a valid subgraph (a matching of two disjoint edges) but is not induced, since it drops the edges $\{2,3\}$ and $\{1,4\}$ that $G$ actually has among these vertices.

Complement. Since $n = 6$, $\binom{6}{2} = 15$, and $|E(\overline{G})| = 15 - 7 = 8$, matching Edge complementarity. Concretely, all $15$ pairs are

Removing the $7$ edges of $E$ leaves

which indeed has $8$ elements. Check the degree identity at vertex $1$: $\deg_G(1) = |\{\{1,2\},\{1,6\},\{1,4\}\}| = 3$, and $\deg_{\overline{G}}(1) = |\{\{1,3\},\{1,5\}\}| = 2$; sum is $5 = n - 1 = 6-1$. ✓. Named families inside $G$. $G$ contains $P_4$ as a subgraph (e.g. $2$–$3$–$4$–$5$, using existing edges $\{2,3\},\{3,4\},\{4,5\}$), and contains $C_4$ as an induced subgraph, as computed above (on $\{1,2,3,4\}$), and contains the full $6$-cycle $C_6$ as a spanning subgraph (drop the chord $\{1,4\}$). $G$ does not contain $K_4$ as a subgraph: a $K_4$ needs $6$ edges among $4$ vertices, but the maximum number of edges $G$ has among any $4$ vertices is $4$ (as seen with $S=\{1,2,3,4\}$), since $G$ has only $7$ edges total spread over $6$ vertices with maximum degree $3$.

Example 2: A graph and its complement, with a clique/independent-set duality. Let $V = \{a,b,c,d,e\}$ and

So $|E| = 5$. Degrees: $\deg(a)=3$ ($b,c,d$), $\deg(b)=2$ ($a,c$), $\deg(c)=3$ ($a,b,e$), $\deg(d)=1$ ($a$), $\deg(e)=1$ ($c$). Is $\{a,b,c\}$ a clique? We check whether $G[\{a,b,c\}] \cong K_3$. The pairs are $\{a,b\}, \{a,c\}, \{b,c\}$ — all three are in $E$. So yes, $\{a,b,c\}$ induces a triangle: $G[\{a,b,c\}] = K_3$. Complement. Here $n=5$ so $\binom{5}{2}=10$, hence $|\overline{E}| = 10 - 5 = 5$. All $10$ pairs on $\{a,b,c,d,e\}$ are

Removing the $5$ edges of $E$ (namely $ab,ac,ad,bc,ce$) leaves

Duality check. Since $\{a,b,c\}$ is a clique in $G$ (all edges present), it must be an independent set in $\overline{G}$ (no edges present): check $ab, ac, bc \notin \overline{E}$ — indeed none of these three appear in $\overline{E}$ above. ✓ This illustrates the general fact that $S$ induces a complete subgraph in $G$ if and only if $S$ induces an edgeless subgraph in $\overline{G}$, an immediate consequence of the complement definition (a pair is an edge of $G$ exactly when it is a non-edge of $\overline{G}$). Named families. Is $G$ itself a path or a cycle? $G$ has $5$ vertices and $5$ edges; $P_5$ would need $4$ edges and $C_5$ would need $5$ edges, so edge count alone does not rule out $C_5$. But $C_5$ requires every vertex to have degree exactly $2$, while here $\deg(d) = 1$ and $\deg(a) = 3$. So $G$ is neither $P_5$ nor $C_5$ nor any relabeling of them — it is a genuinely different graph on $5$ vertices with $5$ edges (a "bull"-like graph: a triangle $a,b,c$ with pendant edges $ad$ and $ce$... actually $d$ hangs off $a$ and $e$ hangs off $c$, two distinct pendants off the triangle).

Harary was not the sole originator of these ideas — complement graphs and complete graphs trace to earlier combinatorics and to the graph-theoretic reformulation of Ramsey's theorem in the 1930s — but his expository and organizational work made graph theory a self-contained subject with a shared, precise vocabulary, rather than a scattered set of results borrowed from topology and combinatorics.