Hello, Codeforces!
(Disclaimer: I know very little about flows and matchings)
An interesting idea that I heard at the University recently was a greedy algorithm to find the maximum matching in a bipartite graph. The idea is simple, at each step take the node with the smallest number of unmatched neighbours (I will call it active degree) and match this node with one of its neighbours. Specifficaly match it with the neighbour whose active degree is the smallest. Update the active degree for all neighbours of the 2 nodes. Repeat until you can't match anything.
Noone in class was able to find a counter example, but we also couldn't prove that it is correct (which it likely isn't).
If anyone would be kind enough to provide a counter example / proof / link to some paper / article I would be very thankful.
Here is a counterexample:
$$$16$$$ nodes (numbered $$$1 - 16$$$), $$$25$$$ edges, nodes $$$1 - 8$$$ are on the left, nodes $$$9 - 16$$$ are on the right.
You can get a perfect matching by matching everything "horizontally", except for pairs $$$(1, 10)$$$ and $$$(2, 9)$$$.
Your greedy algorithm will first choose the edge $$$(1, 9)$$$, since nodes $$$1$$$ and $$$9$$$ are the only ones with degree $$$2$$$.
After choosing this, nodes $$$2, 3, 4, 5$$$ only have nodes $$$11, 12, 13$$$ to pair up with so we can't pair all of nodes $$$2, 3, 4, 5$$$ and thus, we won't get a perfect matching.
Thank you very much, sir