# Flipping all incoming/outgoing edges from a vertex in a DAG

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?

• Consider the graph on the vertices $x,y,z,w$ with edges $x\to y$, $x \to z$, $y \to w$, $z \to w$. This is a DAG. If you reverse the orientation of all edges incident to $y$ then you get a directed square, which is not a DAG. – Yuval Filmus May 16 '17 at 18:01
• @Yuval Filmus Yes, it seems you can only flip all incoming or all outgoing, not both of them at the same time – ghord May 16 '17 at 19:52
• Have you tried proving that the graph remains a DAG? – Yuval Filmus May 16 '17 at 20:25

1. After flipping all incoming(outgoing) edges from vertex v in a DAG G, we get another graph that is not a DAG (it has a cycle).
2. 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 v.
3. Since we flipped directions of all incoming(outgoing) edges from vertex v, all edges incident to vertex v are now outgoing(incoming), so it is not possible for any cycle to go through vertex v, which contradicts 2.