every vertices except two in 2-connected graph can be linearly ordered in a specific way

254 Views Asked by At

Let $s$ and $t$ be vertices in $2$-connected graph $G$, prove that the vertices of $G$ can linearly ordered so that each vertex apart from $s$ and $t$ has a neighbor that is earlier in the order and a neighbor that is later in the order.

I think this is related to ear decomposition of graph $G$ since it's $2$-connected, and I know the number of ears (including initial cycle) in every ear decomposition is $|E(G)| -|V(G)|+1$, but not sure how to proceed after that

1

There are 1 best solutions below

0
On

Start your ear decomposition with a cycle containing both $s$ and $t$. If that cycle has vertices $(s, v_1, v_2, \dots, v_k, t, w_\ell, \dots, w_2, w_1, s)$ then the ordering $$s, v_1, v_2, \dots, v_k, w_1, w_{2}, \dots, w_\ell, t$$ has the property you want - for vertices on that cycle. (Actually, $v_1, v_2, \dots, v_k$ and $w_1, w_2, \dots, w_\ell$ can be interleaved however we like. The property is satisfied as long as both $s \prec v_1 \prec v_2 \prec \dots \prec v_k \prec t$ and $s \prec w_1 \prec w_2 \prec \dots \prec w_k \prec t$ hold).

Then go through the rest of the ear decomposition. Check that as you add each ear, the new vertices on the ear can be inserted into the ordering in such a way that the property you want continues to hold.