Content deleted Content added
m Open access bot: hdl added to citation with #oabot. Tag: Reverted |
→Orientable graphs: clarify that this is not an open ear decomposition |
||
Line 10:
If a graph has a bridge, then it cannot be strongly orientable, for no matter which orientation is chosen for the bridge there will be no path from one of the two endpoints of the bridge to the other.
In the other direction, it is necessary to show that every connected bridgeless graph can be strongly oriented. As Robbins proved, every such graph has a partition into a sequence of subgraphs called "ears", in which the first subgraph in the sequence is a cycle and each subsequent subgraph is a path, with the two path endpoints both belonging to earlier ears in the sequence. (The two path endpoints may be equal, in which case the subgraph is a cycle.) Orienting the edges within each ear so that it forms a directed cycle or a directed path leads to a strongly connected orientation of the overall graph.<ref>{{harvtxt|Gross|Yellen|2006}}.</ref>
==Related results==
| |||