How many copies of $K_3$ in $K_n$ I don't have any idea how to do these questions. Can I have some help ?
$(i)$ How many copies of $K_3$ are there in $K_n$?
I know there are $n$ choose $3$ ways of choosing the $3$ vertices. I could then multiply this by $3!$ to order them. Not sure what to do from there.
$(ii)$ Fix distinct vertices $x$ and $y$ in $K_n$. How many copies of $K_3$ in $K_n$ contain the edge $xy$?
$(iii)$ Fix distinct vertices $x, y$ and $z$ in $K_n$. How many copies of $K_3$ in $K_n$ contain at least one of the edges $xy, yz$ and $xz$?
$(iv)$ Prove that every graph with $6$ vertices and at least $10$ edges contains a copy of $K_3$
 A: Hints for problem (iv).

*

*There is a vertex of degree at least 4 (otherwise $<10$ edges).

*There are at least two neighbors connected by an edge (otherwise $<10$ edges).

From 1 and 2 it follows that the graph has a triangle.
A: Let $[n]=\{1,\dots,n\}$ be the standard vertices and let $\binom{[n]}{2}=\{e\subseteq[n]:|e|=2\}$ be all subsets of $[n]$ of size $2$, viewed as edges $\{i,j\}\in\binom{[n]}{2}$ connecting the vertices $i$ and $j$. Recall that the standard complete graph is $K_n=([n],\binom{[n]}{2})$. In particular, notice that this graph is determined by the choice of the vertices. This means that for a copy $G=(\mathcal V,\mathcal E)$ of $K_n$ we know that $\mathcal E=\binom{\mathcal V}{2}$, i.e. for any choice of two distinct vertices $u,v\in\mathcal V$ the edge $\{i,j\}$ has to be included.

*

*Recall that a graph $G=(\mathcal V,\mathcal E)$ is a copy of $K_3=([3],\binom{[3]}{2})$ in $K_n=([n],\binom{[n]}{2})$ if $\mathcal V\subseteq[n]$ is a subset of $[n]$, $\mathcal E\subseteq\binom{[n]}{2}$ is a subset of $\binom{[n]}{2}$ and $G$ is isomorphic to $K_n$, meaning there exists a bijection $\iota:\mathcal V\rightarrow[3]$ such that $K_3$ is the image of $G$ under the induced graph isomorphism. Put simply, $K_3$ is a triangle and $G$ is a copy of $K_3$ in $K_n$ if $G$ is a triangle in $K_n$. How many $\mathcal V$ can we possibly choose? Well, this is exactly the binomial coefficient $\binom{n}{3}$ since $|\mathcal V|=3$ by the above. For any such choice $\mathcal V\in\binom{[n]}{3}$ notice that $\binom{\mathcal V}{2}\subseteq\binom{[n]}{2}$, meaning that all possible (three) edges connecting vertices in $\mathcal V$ are included in $K_n$, since all edges are included. This means that the copy $G=(\mathcal V,\binom{\mathcal V}{2})$ of $K_3$ is present in $K_n$. This means that for any of the $\binom{n}{3}$ possible choices of $\mathcal V$ we obtain exactly one copy of $K_3$. So, the answer is $\binom{n}{3}$.

*If a copy $G=(\mathcal V,\mathcal E)$ of $K_3$ includes the edge $\{x,y\}\in\mathcal E$, then it has to include $x,y\in\mathcal V$ as vertices. But since $G$ is a copy of $K_3$, we have $|\mathcal V|=3$, so we can only choose one additional vertex $z$. For this, we have $n-2$ remaining choices. As seen in the first item, any such choice gives exactly one copy of $K_3$, so the answer is $n-2$.

*Using inclusion-exclusion we take $3(n-2)$, but then we have to subtract all copies that include two of the edges. But if a copy $G=(\mathcal V,\mathcal E)$ includes two of the edges, say $\{x,y\}$ and $\{x,z\}$, then it includes $x,y,z\in\mathcal V$ and hence we have $\mathcal V=\{x,y,z\}$, and there is exactly one such copy of $K_3$. The same is true for the other pairs of edges, so the only copy which includes two edges is $G=(\{x,y,z\},\binom{\{x,y,z\}}{2})$, and $G$ is also the only graph that includes all three edges. Inclusion-Exclusion gives $3\binom{n}{3}-3\cdot 1+1$.

*For a graph $G=(\mathcal V,\mathcal E)$ and $v\in\mathcal V$ let $d(v)=|\{u\in\mathcal V:\{u,v\}\in\mathcal E\}$ be the degree of $v$ in $G$. Notice that $\sum_{v\in\mathcal V}d(v)=\sum_{v\in\mathcal V}\sum_{\{u,v\}\in\mathcal E}1=\sum_{e\in\mathcal E}\sum_{v\in e}1=2|\mathcal E|$, meaning that the sum of the degrees is twice the number of edges, the handshaking lemma. So, if $|\mathcal V|=6$ and all degrees are smaller than four, then we have $2|\mathcal E|\le 6\cdot 3=18$ and thereby $|\mathcal E|\le 9$. This shows that for $G$ with $|\mathcal E|\ge 10$ there exists a vertex with at least degree $4$. Let $v\in\mathcal V$ be such that $d(v)\ge 4$ and let $v_1,\dots,v_4$ be four neighbors. Let $v_5$ be the remaining, sixth vertex. Even if $v_5$ shares edges with all other vertices, we have still only considered at most $4+5=9$ edges so far. The tenth edge cannot include $v_5$ since we considered all these edges already, and can hence not include $v$ since we considered $\{v,v_1\}$ to $\{v,v_4\}$ and $\{v,v_5\}$ includes $v_5$, so the tenth edge $e$ must be a subset of $\{v_1,\dots,v_4\}$. But then $G'=\{\mathcal V',\mathcal E'\}$ with $\mathcal V'=\{v\}\cup e$ and $\mathcal E'=\binom{\mathcal V'}{2}$ is a copy of $K_3$.

