Define $G(n,\frac12)$ to be a graph on $n$ vertices where each edge has a $\frac12$ probability of being formed. We may compute the number of subgraphs of $G(n,\frac12)$ isomorphic to, say, $K_3$ as follows.
$K_n$ has $\binom{n}{3}$ such subgraphs; we can enumerate them as $H_1,\cdots, H_{\binom{n}{3}}$ and define $$X_i=\begin{cases} 1 & H_i\subseteq G(n,\frac12) \\ 0 & \text{otherwise}\end{cases}$$ to obtain $\mathbb{E}[X] = \sum_i \mathbb{E}[X_i] = \binom{n}{3}\left(\frac12\right)^3$.
But how can we count the number of induced subgraphs isomorphic to $K_3$?
It appears that the graph removal lemma gives me what I want for very special cases, but it is beyond the scope of my graph theory course. Surely there has to be a simpler approach when we are interested in "simple" subgraphs like $P_n$, $C_n$, or $K_n$.
Best Answer
I think this is right...
For any smaller graph $H$, with $k$ vertices and $e$ edges, $$ \begin{align} \mathbb E[\text{# subgraphs $\cong H$}] &=\binom{n}k\frac{k!}{|\operatorname{Aut}(H)|}(1/2)^{e} \\ \mathbb E[\text{# induced subgraphs $\cong H$}] &=\binom{n}k\frac{k!}{|\operatorname{Aut}(H)|}(1/2)^{k(k-1)/2} \end{align} $$ $\binom{n}k\frac{k!}{|\operatorname{Aut}(H)|}$ counts the number places $H$ can appear in $G$; you choose the vertices, given them names, and note that two re-namings which result in the same $H$ should not be counted twice. The only difference is that having an induced subgraph requires the edges not present in $H$ to not be present in $G$ as well, leading to extra factors of $1/2$.
Some examples:
If $H$ is a complete graph, then $|\operatorname{Aut}(H)|=k!$, so you get $\binom{n}{k}(1/2)^{k(k-1)/2}$ in either case.
If $H$ is a cycle, then $|\operatorname{Aut}(H)|=(k-1)!$ so you get either $\binom{n}{k}\cdot k(1/2)^{n}$ subgraphs, and $\binom{n}{k}\cdot k(1/2)^{n(n-1)/2}$ induced subgraphs, on average.