# How to answer this graph theory question?

Okay so let me define some terms before I ask my problem:

Let $K_n$ denote the complete graph on $n$ vertices with $n\geq 2$ and let $C_3$ be a cycle of length $3$ (a triangle).

Suppose $x,y,z$ are distinct vertices in $K_n$:

How many copies of $C_3$ are there in $K_n$ which contain at least one of the edges $xy$, $yz$ and $xz$?

My thoughts are like this:

Picking any edge from $xy$, $yz$ and $xz$ gives $n-2$ possible copies of $C_3$ (Just select the two other edges to meet at the same point and since this is a complete graph there must be $n-2$ of these.)

This is the same for the other two edges that you did not select.

So in total there are $3(n-2)$ copies but this overcounts so we need to remove the overcounting.

Choosing two edges from $xy$, $yz$ and $xz$ determines the triangle $xyz$ and so we need to remove this $3$ times and then add it back one last time. (See inclusion exclusion principle for $3$ sets), thus there are $3n-8$ total triangles in $K_n$.

Is this along the right lines?

I think that you removed one-too-many when you were accounting for overcounting. Specifically you removed the copy of $C_3$ made up of exactly the edges $xy$, $yz$, and $xz$.

I thought about the problem by classifying the copies of $C_3$ by how many of edges in $\{xy, yz, xz\}$ it contains.

• There is only $1$ copy of $C_3$ that contains all three of these edges.
• There are no copies of $C_3$ with exactly two edges (else it would also have the third).
• For each single edge in $\{xy, yz, xz\}$ there are exactly $(n-3)$ more vertices in $K_n$ that you can use to complete the $C_3$. So this gives us $3(n-3)$ copies of $C_3$.

This gives us a total of $1 + 3(n-3)$.

• Are you saying the answer should be $3n-8$? May 21 '15 at 14:21
• @Daniel, That's what I'm thinking. I'm expanding my post to include my reasoning. May 21 '15 at 14:22
• I agree with you. Using the IE for $3$ sets I have $3(n-2)-3+1=3n-8$ I forgot to add the last one back on. May 21 '15 at 14:23
• Great, many thanks. May 21 '15 at 14:28