1
$\begingroup$

Note: This is almost certainly an elementary problem with a well known solution. Therefore pointers to existing references will be accepted as good answers.

Question: Given a cycle with exactly $n$ vertices, how many distinct chords are possible?

This question is motivated by the definition of chordal graph, which only requires the cycles in the graph to have chords if the cycles have four or more vertices.

Doodling on paper I realized that this is because, for the smallest possible number of vertices in a cycle, namely three, the existence of a chord is impossible. But as soon as the cycle contains at least four vertices the existence of a chord is possible.

For the four-vertex cycle, it seems that there are only two possible chords. Since a chord is formed between two distinct vertices in a cycle, and $2$ might be the first term in a sequence of coefficients of the form $\binom{f(n)}{2}$ for some $f(n)$, I thought that the solution might be similar to the handshake problem and involve $\binom{n}{2}$ or $\binom{n-1}{2}$ somehow.

But this seems to fail already when $n = 5$, because instead of getting $\binom{4}{2} = 6$, which I had expected, instead I counted 5 distinct chords. So then I thought that maybe the answer is the Catalan numbers, since after $1$ they start with $2,5,\dots$, have a form similar to the $\binom{n}{2}$ from the handshake problem, and show up in all sorts of unexpected places.

But this conjecture also fails, since for the cycle with $n=6$ vertices I counted 9 (or maybe 8) distinct chords, and this obviously isn't the third non-unit Catalan number 14, nor is it $\binom{5}{2} = 10$. I somewhat expect the numbers/sequences to differ for odd and even number of vertices however, for a reason analogous to why a graph is Eulerian if and only if each of its vertices has even degree.

I would like to know the answer not only out of sheer curiosity, but also for some intuitive insight into how one can then go on to count the number of possible chordal completions of a graph (which one then uses to calculate the treewidth) -- that is all outside the scope of this question however.

$\endgroup$
  • 1
    $\begingroup$ The answer is $n(n-3)/2$. $\endgroup$ – Yuval Filmus Dec 1 '17 at 7:01
2
$\begingroup$

A chord consists of a vertex $i$ and a different nonadjacent vertex $j$. There are $n$ options for $i$, and $n-3$ options for $j$ (since we can't choose $i$ or any of its two adjacent vertices). Since we can switch $i,j$ and get the same chord, we have to divide by 2. Overall, we get that the number of chords is $$ \frac{n(n-3)}{2}. $$ When $n=3,4,5,6$, this gives $0,2,5,9$, matching your values.

$\endgroup$
1
$\begingroup$

Based on the Online Encyclopedia of Integer Sequences page on this sequence and it’s references, it seems that the answer to this question is not known.

The answer is known for labeled chordal graphs via a rather non-elementary approach.

$\endgroup$

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.