I'm working on a problem where I have a directed acyclic graph and I need to repeatedly flip all incoming (or outgoing, or both incoming and outgoing) edges from a single vertex. I think that resulting graph is still a DAG. Am I correct?
This doesn't hold if we flip both outgoing and incoming edges as shown by @Yuval Filmus.
Here is my try of a proof by contradiction for only flipping outgoing of incoming edges (sorry if it's too informal):
- After flipping all incoming(outgoing) edges from vertex
vin a DAG
G, we get another graph that is not a DAG (it has a cycle).
- Since we only changed the direction of the vertices incident to
v, the only way we loose the acyclic property is if there is a new cycle going through vertex
- Since we flipped directions of all incoming(outgoing) edges from vertex
v, all edges incident to vertex
vare now outgoing(incoming), so it is not possible for any cycle to go through vertex
v, which contradicts 2.