2-connected graph game Problem 7.2.53 in Combinatorial Mathematics by Douglas B. West.

*

*Complete question is:

Alice and Bob play a game on 2-connected $n$-vertex graph $G$. Alice picks vertices $u$ and $v$. Next Bob orients up to $f(n)$ of the edges. Alice then orients the remaining edges and selects an edge $e$, which may have been oriented by her or by Bob. If the orientation contains a $u,v$-path through $e$, then Bob wins; otherwise Alice wins. Prove that the least $f(n)$ such that Bob always has a winning strategy is $2n - 3$. (Kerimov [2009]).


*My effort:

I am trying to consider the construction of 2-connected graph:

(Proposition) A graph is 2-connected if and only if it can be constructed from a cycle by successively adding $H$-paths to graph $H$ already constructed.

But I can not determine the edges I really need. Please give me some hint if possible!
 A: (Original answer by my TA, really impressive)
First, we can use triangle $(n=3)$ show that $2n-4$ is not enough: for any two vertices $u,v$, if Bob choose $uv$ and another edge $uw$, then Alice just needs to choose $vw$ as $e$ and orient it such that $u-w-v$ can not be a path; if Bob choose $uw$ and $vw$, then Alice only needs to orient $uv$ as $v-u$ and choose $e$ as $vu$.
Now we prove that Bob always has a winning strategy when he can orient $2n-3$ edges. For that, we need to prove a $s,t$-numbering lemma:

Exercise 7.2.51 in Combinatorial Mathematics by Douglas B. West.
Let $s$ and $t$ be vertices in a 2-connected graph $G$. Prove that the vertices of $G$ can be linearly ordered so that each vertex outside $\{s,t\}$ has a neighbor that is earlier in the order and a neighbor that is later in the order. (Comment: This is called an $s,t$-numbering of $G$.)

(To be done)
Then the vertices of $G$ can be linearly ordered so that each vertex other than $u,v$ has a neighbor that is earlier in order and a neighbor that is later in order.
If $uv \in G$ then Bob orients it from $u$ to $v$. For any vertex $w$ other than $u, v$, pick its smallest neighbor $s$ and largest neighbour $t$. Bob orients $s w$ from $s$ to $w$ and orients $w t$ from $w$ to $t$. These add up to no more than $1+2\times(n-2)=2n-3$ edges. Next we prove there is always a $u, v$-path through $e$. If $e$ is oriented by Bob, then we may extend both ends following Bob's orientation and eventually we will reach $u$ and $v$. If $e$ is oriented by Alice from the smaller endpoint to the larger one then the same method works. And finally, if $e$ is oriented from $x$ to $y$ where $x>y$, then this fact itself shows that $x$ has a neighbor $x^{\prime}$ smaller than $y$ and $y$ has a neighbor $y^{\prime}$ larger than $x$. So we may follow Bob's orientation from $u$ to $x$ through $x^{\prime}$, go from $x$ to $y$ and then follow Bob's orientation from $y$ to $v$ through $y^{\prime}$. Since $x^{\prime}<y$ and $y^{\prime}>x$, the trail we constructed above is indeed a path.
