2
$\begingroup$

Suppose we put $n$ point on the circumference of a circle, and color them red and blue. Show that there are at most $\lfloor \frac{3n-4}{2} \rfloor$ chords connecting point of different colors that do not intersect in the interior of the circle.

Do you have any suggestions how to approach this problem (it is taken from M. Aigner, Discrete Mathematics). I am stuck on this problem. One idea I have is that a subset of red and blue vertices form an $K_{3,2}$ (i.e the complete bipartie graph), then we must have at least one intersection. So now a general approach might be to show that $n$ points with more than $\lfloor \frac{3n-4}{2} \rfloor$ chords connecting differently colored points implies that five points induce the $K_{3,2}$. But the only upper bound on the number of chords I get by this is $5n/6$ by the observation if five points have more than six chords, they form the $K_{3,2}$. But this bound is not good enough.

$\endgroup$
  • $\begingroup$ It might be helpful to note that $\left\lfloor\dfrac{3n-4}2\right\rfloor=(n-2)+\left\lfloor\dfrac n2\right\rfloor$ $\endgroup$ – Prasun Biswas Feb 8 '18 at 16:43
2
$\begingroup$

One approach would be to start with the reasonably well-known result that a bipartite planar graph on $n$ vertices has at most $2n-4$ edges. (This follows from Euler's formula and the observation that each face must have at least four sides.)

In this problem, the graph of all the chords is obviously a bipartite planar graph... but this bound is too weak: we want something closer to $\frac32n$. So we can take advantage of the fact that all $n$ vertices lie on a circle and all edges can be drawn in the interior.

Without loss of generality, there are at least $\lceil \frac n2 \rceil$ red points around the circle. So add a new vertex outside the circle and connect it to all the red points. The result is a bipartite planar graph on $n+1$ vertices, so it has at most $2n-2$ edges, and working backwards, we can bound the number of edges in the original graph. This should give exactly $\lfloor \frac{3n}{2} - 2\rfloor$ edges when you do the math.


Alternatively, here's a different argument that doesn't rely on planar graphs and Euler's formula.

Induct on $n$. The bound is tight for all $n \le 4$ by casework. (These base cases are trivial but important: they're the only reason we get a bound with $\frac32n$ and not $2n$ or $\frac74n$ or anything else like that.)

Take an arbitrary chord between non-adjacent points around the circle. (If no such chord exists, we get a bound of $n$, which is better than what we want to show when $n > 4$.) It divides the circle into two polygons that don't interact at all except for sharing this chord. If one contains $k$ points, the other contains $n-k+2$, so the total number of chords they have is (by the inductive hypothesis) at most $$ \left\lfloor \frac{3k-4}{2} \right\rfloor + \left\lfloor \frac{3(n-k+2)-4}{2}\right\rfloor - 1 $$ and by doing some arithmetic, we can simplify this to at most the correct bound for $n$. (Tip: we can drop all the floors around everything, since we know that the final answer is an integer, and so if the upper bound is a fraction, it can be rounded down.) So, by induction,the claim holds for all $n$.

Note: it bothered me a lot in this proof that we don't seem to use the colors at all before I figured out why. We do, we just use them in the base cases. In general, for this proof to work, the bound we prove has to be of the form $a(n-2)+1$ for some $a$; here, it's $\frac32(n-2)+1$. The best values of $a$ for the base cases determine what $a$ is in general, and we determine the number of base cases we need by noting that the "$n$ is a better bound" step of the proof only works for $n > \frac{2a-1}{a-1}$.

$\endgroup$
  • $\begingroup$ I really like your argument, but I still would like to see a different answer (so I wait a little with accepting it), because the problem appears after chapter one of Aigners book, and Eulers formula and planar graphs are not mentioned there. So maybe there is a solution just using notions introduced in the book so far... $\endgroup$ – StefanH Feb 8 '18 at 16:59
  • $\begingroup$ There is! Turns out we can just induct; see my edit. $\endgroup$ – Misha Lavrov Feb 8 '18 at 17:36

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.