Isomorphism and Subgraphs

Let $G$ have vertices $1,\ldots,5$ and edges $12, 13, 23, 34, 45$ (a triangle on $1,2,3$ with a path hanging off through $4$ to $5$). The subgraph induced by $S=\{1,2,3,4\}$ keeps every edge of $G$ with both ends in $S$: that is $12, 13, 23, 34$ — the triangle plus the edge to $4$, but nothing touching $5$. Compare the spanning subgraph $H$ with $V(H)=\{1,\ldots,5\}$ and edges $12, 34, 45$ only: $H$ is spanning (it has all 5 vertices) but NOT induced by anything, since $1,2,3$ are all present yet edge $13$ and $23$ are missing even though both ends lie in $H$.

Take $K_{2,3}$ with parts $\{a,b\}$ and $\{c,d,e\}$: every cross pair is an edge, $ac,ad,ae,bc,bd,be$, six edges in all. Of the $\binom52=10$ possible pairs on 5 vertices, the four NOT used are $ab$ (within the first part) and $cd,ce,de$ (within the second). So $\overline{K_{2,3}}$ has exactly those four edges — a single edge $ab$ together with a disjoint triangle $cde$: $\overline{K_{2,3}} \cong K_2 \cup K_3$, two cliques with no edges between them. The same argument shows $\overline{K_{m,n}} \cong K_m \cup K_n$ for any complete bipartite graph.

How many spanning subgraphs does the triangle $K_3$ (vertices $1,2,3$, edges $12,13,23$) have? A spanning subgraph keeps all 3 vertices and any subset of the 3 edges, and every edge subset is allowed since removing edges can never break the "both ends present" rule. So the count is the number of subsets of a 3-element set, $2^3=8$: the empty graph, three graphs with one edge, three with two edges (each a path on all 3 vertices), and $K_3$ itself, and $1+3+3+1=8$ checks against $2^3$.

Let $G_1$ have vertices $1,\ldots,5$ and edges $12,23,34,45,15$ — the standard pentagon. Let $G_2$ have vertices $a,\ldots,e$ and edges listed out of order: $ad, dc, cb, be, ea$. Reading $G_2$'s edges in sequence traces the cycle $a\text{-}d\text{-}c\text{-}b\text{-}e\text{-}a$, so both graphs are 5-cycles. The map $\varphi: 1\mapsto a,\, 2\mapsto d,\, 3\mapsto c,\, 4\mapsto b,\, 5\mapsto e$ sends $12\mapsto ad$, $23\mapsto dc$, $34\mapsto cb$, $45\mapsto be$, $15\mapsto ea$ — every edge of $G_1$ lands on an edge of $G_2$, and since both have exactly 5 edges none are left over, so $\varphi$ is an isomorphism.

The star $K_{1,3}$ (center $x$, leaves $p,q,r$, edges $xp,xq,xr$) and the path $P_4$ ($1\text{-}2\text{-}3\text{-}4$, edges $12,23,34$) both have 4 vertices and 3 edges. But $K_{1,3}$ has a vertex of degree 3 and three of degree 1, while every vertex of $P_4$ has degree 1 or 2 — no vertex of $P_4$ has degree 3. Since an isomorphism would have to send the degree-3 vertex of $K_{1,3}$ to a vertex of the same degree in $P_4$, and none exists, $K_{1,3} \not\cong P_4$.

How many automorphisms does $C_4$ (vertices $1,2,3,4$, edges $12,23,34,14$) have? An automorphism is a relabeling of $1,2,3,4$ that preserves this exact edge set. Rotating the labels around the cycle ($1,2,3,4 \mapsto 2,3,4,1$, etc.) gives 4 automorphisms, and reflecting (e.g. fixing $1,3$ and swapping $2,4$) gives 4 more — 8 in total, matching the 8 symmetries (4 rotations, 4 reflections) of a square. No other relabeling can work: a vertex and its two cycle-neighbors must go to a vertex and its two neighbors, which pins down the whole map once one edge's image is chosen, and there are exactly $4 \times 2 = 8$ ways to choose it.

$C_6$ (vertices $1,\ldots,6$, edges $12,23,34,45,56,16$) and $2C_3$ (two disjoint triangles $123$ and $456$: edges $12,23,13,45,56,46$) both have 6 vertices, 6 edges, and every vertex of degree 2 — identical degree sequences. But $C_6$ is a single connected cycle, while $2C_3$ splits into two components. "Number of connected components" is an invariant (an isomorphism maps components to components), and $1 \ne 2$, so $C_6 \not\cong 2C_3$.

The complete bipartite graph $K_{3,3}$ (parts $\{1,2,3\}$, $\{4,5,6\}$, all 9 cross edges) and the triangular prism (two triangles $123$, $456$ joined by a matching $14,25,36$, also 9 edges) are both 3-regular on 6 vertices — same $|V|$, $|E|$, and degree sequence. $K_{3,3}$ has no triangle at all: every edge runs between the two parts, so three vertices forming a triangle would need an edge within a part, and there is none. The prism has exactly 2 triangles ($123$ and $456$; the matching edges join the triangles but create no new one, e.g. $1,2,5$ has edges $12,25$ but not $15$). Since $0 \ne 2$, the graphs are not isomorphic even though every invariant checked so far agreed.

Up to isomorphism there are only 3 graphs on 4 vertices with exactly 3 edges, and the degree sequence sorts them instantly: $(3,1,1,1)$ is the star $K_{1,3}$; $(2,2,1,1)$ is the path $P_4$; $(2,2,2,0)$ is the triangle $K_3$ plus an isolated vertex. Every other way of placing 3 edges on 4 vertices is a relabeling of one of these three, since there is no room left for a fourth shape once these degree sequences are fixed.

Let $G = P_4$: vertices $1,2,3,4$, edges $12,23,34$. Of the $\binom42=6$ pairs, the 3 not used are $13,14,24$, so $\overline G$ has edges $13,14,24$. Those three edges form the path $3\text{-}1\text{-}4\text{-}2$ (consecutive pairs $13,14,24$ share endpoints in a chain) — a path on 4 vertices, the same shape as $G$. The relabeling $\varphi: 1\mapsto3,\,2\mapsto1,\,3\mapsto4,\,4\mapsto2$ carries $G$'s edges $12,23,34$ to $31,14,42$, exactly $\overline G$'s edge set. So $P_4 \cong \overline{P_4}$.

Let $G = C_5$: vertices $1,\ldots,5$, edges $12,23,34,45,15$. The $\binom52=10$ pairs split into these 5 and the other 5: $13,14,24,25,35$. Tracing adjacencies in $\overline G$ — $1$ to $3,4$; $3$ to $1,5$; $5$ to $2,3$; $2$ to $4,5$; $4$ to $1,2$ — links up into the single cycle $1\text{-}3\text{-}5\text{-}2\text{-}4\text{-}1$, another 5-cycle. So $\overline{C_5} \cong C_5$ as well: $C_5$ is the smallest self-complementary graph with no isolated structure to exploit, unlike $P_4$.

Check $\binom n2$ for $n=3,\ldots,8$: $3,6,10,15,21,28$. Only the even values survive the necessary condition: $6$ ($n=4$), $10$ ($n=5$), and $28$ ($n=8$); the odd values $3,15,21$ (at $n=3,6,7$) are impossible. That matches $n\equiv0,1\pmod4$ exactly: $4\equiv0$, $5\equiv1$, $8\equiv0$, while $3,6,7\equiv3,2,3\pmod4$.

On vertices $1,2,3$ there are $2^{\binom32}=2^3=8$ labeled graphs (independently include or exclude $12,13,23$), and every one of them is a relabeling of exactly one of 4 shapes: the empty graph (1 labeled copy), a single edge (3 labeled copies — one for each edge choice), a path on all 3 vertices (3 labeled copies — one for each choice of the missing edge), or the full triangle (1 labeled copy). These counts total $1+3+3+1=8$, matching $2^3$ exactly, and there are $\mathbf{4}$ shapes up to isomorphism.

On 4 vertices, $\binom42=6$, so there are $2^6=64$ labeled graphs. Sorting these 64 by isomorphism class (by hand or by computer, checking every candidate pair of graphs for a relabeling) gives exactly 11 shapes — far fewer than $64/4! = 64/24 \approx 2.67$, which is not even an integer, let alone the right answer.

How many labeled graphs on 5 vertices have exactly 3 edges, and how many shapes do they represent up to isomorphism? There are $\binom{10}{3}=120$ ways to choose 3 of the $\binom52=10$ possible edges, so 120 labeled graphs. Up to isomorphism there are exactly 4 shapes: a triangle plus 2 isolated vertices, a path $P_4$ plus 1 isolated vertex, a star $K_{1,3}$ plus 1 isolated vertex, and a disjoint path-plus-edge $P_3 \cup K_2$ using all 5 vertices with none isolated — every other placement of 3 edges on 5 vertices is a relabeling of one of these.