Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider $C$, a family of intervals on $R$, such that each $p ∈ R$ is contained in at most $m$ of these intervals. Prove that there is a partition of $C$ into $m$ classes $C_1, ..., C_m$ so that each $C_i$ consists of pairwise disjoint intervals.

My idea is to represent the family of intervals as a bipartite graph, $B$. Then, the problem just becomes finding a partition of the edge set of $B$ into $m$ disjoint matchings, which by König's theorem is equivalent to showing that the maximum degree of a vertex in $B$ is $m$. However, I am at a loss on how to represent this interval graph as a bipartite graph.

NOTE: I'm looking for a graph theoretic way to solve this!

share|improve this question

1 Answer 1

I don't know why you want to use bipartite graphs here. This problem is easily solved with direct greedy approach and induction. Just split $C$ into $C_1$ and $C'$ such that for each $p \in \mathbb{R}$ there is at most $m-1$ intervals $C'$ that contain $p$. Repeat until done.

To give you some hint: Let $[l_1,r_1] \in C_1$, then pick an interval $[l_2,r_2] \in C$ such that its smaller end is the closest possible to $r_1$, that is, $l_2 = \min \{ l \mid [l,r] \in C, r_1 < l\}$. We know that at $r_1$ there are at most $m$ intervals, so for $p \in (r_1,l_2)$ we have at most $m-1$ intervals (note that in-between $(r_1,l_2)$ no new interval could have started because $l_2$ is minimal).

Good luck!

share|improve this answer
That is how I would immediately approach it as well. However, this was a fun extra exercise given by my Extremal Combinatorics professor, so I'm assuming that there has to be a graph theoretic way to solve this as well. Sorry, should've made that more explicit in the original post... –  wemblem Mar 13 '13 at 22:46
On further thought, maybe there is no way to do this using a graph theoretic approach? Hmm... –  wemblem Mar 14 '13 at 9:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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