Orientation digraph question

461 Views Asked by At

Let $G$ be nontrivial connected graph without bridge

a) show that for every edge $e$ of $G$ and for every orientation of $e$, there exist an orientation of the remaining edges of $G$ such that the resulting digraph is strong

b) Show that a) need not to be true if we begin with an orientation of 2 edges of $G$

Robbin theorem: A non trivial graph $G$ has a strong orientation if and only if $G$ is 2-edge-connected.

Since $G$ is a nontrivial connected graph without bridge, by the Robbin theorem, $G$ contain a strong orientation $D$. Meaning $D$ has a closed spanning walk $W=u_1, u_2, ... , u_k ,u_1$

The book told me to consider the converse of $D$, so if I trace back and I got $\vec{D}$ contain the walk $W'=u_1, u_k ,u_{k-1},...,u_2, u_1$.

But I still can't see how this can help me

1

There are 1 best solutions below

0
On BEST ANSWER

For part $A$ use this result. if a digraph $G$ is strong then it is also strong if we reverse the direction of all the arrows. Proof: a path from $a$ to $b$ becomes a path from $b$ to $a$ and visceversa.

This proves part $A$ since by the Robbin theorem $G$ contains a strong orientation, but the reversal of that orientation is also strong. and these have an opposite direction in all edges.

Part $B$ consider the triangle graph, it has a strong orientation (the cycle). However if we direct two of its edges to a singe vertex it can no longer be made strong since one of the vertices will have out-degree zero.