1
$\begingroup$

According to theorem 3.4, a nontrivial graph G has a strong orientation if and only if G is connected and contain no bridges

a)Prove that if $G$ is an nontrivial connected graph with at most 2 bridges, then there exists an orientation $D$ of $G$ having the property that if $u$ and $v$ are any 2 vertices of $D$, there is either a $u-v$ path or a $v-u$ path

b) Show that the statement in a), is false if G contain 3 bridges

for part a) I know that if $G$ contain zero bridge then we are done. So I only need to consider 2 cases

Case 1: $G$ has exactly one bridge

Case 2: $G$ has exactly 2 bridges

For Case 1: Let $D$ be construct by connecting a vertex $v$ to $C_n$ with every arc has same direction. The direction of the edge incident to $v$ doesn't matter, because either way, we still have either a $u-v$ path or a $v-u$ path

For case 2: I use the same graph in case one and add one more vertex called $w$ and connect it to $v$, the edge incident to $w$ must have same direction to the edge connected $v$ and $C_n$, then I will have either a $u-v$ path or a $v-u$ path

for part b) I can't see why it's false if there is 3 bridges, I can repeat case 2, and add another vertex to $w$, can't I?

$\endgroup$
1
  • $\begingroup$ You did something wrong. The theorem states "then there exists an orientation", not "then for any orientation". Which means that drawing a graph and assigning an orientation is not a counterexample. $\endgroup$
    – Arthur
    Commented Nov 5, 2014 at 0:14

1 Answer 1

1
$\begingroup$

consider $K_{1,3}$, the statement is false, no matter how you assign the direction of the arc

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .