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.

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=1 \ldots n} $ 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 have no common end-points or be identical.

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
I do not think I understand the question. You pick one edge from each graph, and each pair of edges picked, must either be distinct, or the same, doesn't that include all sets of edges? – utdiscant Mar 16 '12 at 17:31
$e_i \cap e_j = \emptyset$ means that the two edges do not share an endpoint vertex, which does not follow automatically if they are "just" distinct. – Jesko Hüttenhain Mar 16 '12 at 17:57
In that case, the sentence " Edges e1 and e2 chosen for any two graphs need to either be non-overlapping or identiacal." should probably be "Edges e1 and e2 chosen for any two graphs need to either have no endpoint in common, or identical." – utdiscant Mar 16 '12 at 18:22
@utdiscant: I prefer your terminology, but some people prefer to treat an edge of a graph as a set of two vertices, in which case the wording of the question is fine. – Tsuyoshi Ito Mar 16 '12 at 19:24
Yes, sorry for the confusion. I'm going to edit the question to include your suggestions. – julkiewicz Mar 16 '12 at 20:09

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.