2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
4
  • $\begingroup$ Are you saying the answer should be $3n-8$? $\endgroup$
    – Daniel
    May 21 '15 at 14:21
  • $\begingroup$ @Daniel, That's what I'm thinking. I'm expanding my post to include my reasoning. $\endgroup$ May 21 '15 at 14:22
  • $\begingroup$ 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. $\endgroup$
    – Daniel
    May 21 '15 at 14:23
  • $\begingroup$ Great, many thanks. $\endgroup$
    – Daniel
    May 21 '15 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.