Let $K_{4}^{-}$ be the graph obtained from $K_{4}$ by deleting an edge. How many subgraphs of $K_{n}$ are isomorphic to $K_{4}^{-}$?

Question

The answer from my notes is ${n \choose {2, 2, n-4}}$. But what am I choosing? What does the first "2" represent? The second "2"? What is $n-4$?

And what is the general process/logic to solve this kind of problems?

Answer 1

Let $S$ be the set of all $K_4^-$-subgraphs of $K_n$. We can identify each $H\in S$ with a set $\{a,b,c,d\}$ of four vertices of $K_n$ and a pair $e$ of points among the four chosen vertices. That is, $H$ is given by the vertex-induced subgraph of $K_4$ on $\{a,b,c,d\}$ minus the edge $e$. Show that this identification is a 1-1 correspondence. Hence, the number of $K_4^-$-subgraphs of $K_n$ is then $$\binom{n}{4}\binom{4}{2}=\binom{n}{2,2,n-4}.$$

Here is another solution which should answer your question about what $2$, $2$, and $n-4$ represent. We can identify $S$ with a partition of the vertex set of $K_n$ into three subsets $A,B,C$ such that $|A|=2$, $|B|=2$, and $|C|=n-4$. That is, each $H\in S$ is identified with the vertex-induced subgraph of $K_4$ on $A\cup B$ minus the edge given by $B$. The number of partitions, which equals the number of elements of $S$, is then $\binom{n}{2,2,n-4}$.