Combined Round
Advanced Round
Monitoring Beavers
fix the set of flips
if each vertex is connected by these edges to a node with initial in-degree > 1, then it’s possible
proof by induction: select any edge such that has in-degree > 1. what happens when we flip :
- if there are any edges going into , has in-degree at least 2 which means all vertices that relied on edge can instead use instead.
- if in-degree of is still > 1 and/or there are no other edges that must be flipped, everything is fine. otherwise, there must be an edge that must be flipped. therefore, paths that rely on can instead go to . how to prove that didn’t depend on previously? i guess we have to flip all cycles first