MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have the following problem:

Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs. I would like to find a "system of representative edges" $ f : \mathcal{G} \rightarrow \bigcup_{i} E(G_{i}) $ such that $ f(G_{i}) \in E(G_{i}) $ and for each $ i, j $ either $ f(G_{i}) = f(G_{j}) $ or $ f(G_{i}) \cap f(G_{j}) = \emptyset $.

In other words, out of each graph we choose one representative edge. Edges $ e_{1} $ and $ e_{2} $ chosen for any two graphs need to either be non-overlapping or identiacal.

This clearly looks very similar to special case of a system of distinct representatives for hypergraphs. However, as noted above, in my case the edges need not be distinct.

An even more specialized case of this problem, where each $ G_{i} $ is a biclique naturally emerges when considering CNF formulae (in this case the two partitions contain positive and negative literals respectively).

Questions: Has such or similar problem been considered in the literature? What theorems apart from KÅ‘nig's theorem and Hall's marriage theorem could serve as existence criteria or analysis tools for the presented problem.

I will be most grateful for your help.

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.