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！