0
$\begingroup$

Let $n\geq 3$ be an integer, set $[n] = \{1,\ldots,n\}$ and let $G=([n],E)$ be an undirected connected bridgeless graph. Is there an orientation (explanation below) of $G$ such that for all $a\neq b\in [n]$ there is a directed path leading from $a$ to $b$?

An orientation of $G=([n],E)$ is a directed graph $G_d=([n], E_d)$ with $E_d \subseteq [n]\times[n]$ where for every $\{x,y\} \in E$ exactly one of $\big\{(x,y),(y,x)\big\}$ is a member of $E_d$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Yes. This is known as Robbins' theorem.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Oh wow - thanks for this quick answer!! I somehow failed to find this in my Google searches... $\endgroup$
    – Dominic van der Zypen
    Commented Feb 19, 2018 at 12:45

You must log in to answer this question.

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