Computing expected number of induced subgraphs of $G(n,\frac12)$ without graph removal lemma. 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$.
 A: 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.
