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

Given a n-regular multigraph (multiple edges incident to the same two nodes are allowed), assume n is even. We try to assign each edge to one of its two end nodes, following a simple greedy rule: for each edge, check how many edges has been assigned to the two end nodes, and assign the edge to the end node with smaller edges. Breaking tie randomly.

Question: Assign the edges in arbitrary order, and each node will have n/2 edges assigned to them. Is it true or not? give proof or counter example.

I‘ve been stuck on this for days。 Thank you all for help!

share|cite|improve this question
It's definitely false if n is odd. – Tony Huynh Jul 13 '11 at 20:17
Does look like homework. – Igor Rivin Jul 13 '11 at 22:31
Is this of interest to research mathematicians, as per the faq? I'm not convinced. Voting to close. – Gerry Myerson Jul 14 '11 at 5:15

It is false for a $C_4$ or for a cube of any dimension. And it looks like homework.

share|cite|improve this answer

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.