Robbins' theorem: Difference between revisions

Revision as of 07:48, 7 July 2014

Revision as of 07:51, 7 July 2014

Line 1:

{{otheruses4|RobbinRobbins's theorem in graph theory|Robin's theorem in number theory|divisor function}}

In [[graph theory]], '''Robbins' theorem''', named after {{harvs|first=Herbert|last=Robbins|authorlink=Herbert Robbins|year=1939|txt}}, states that the graphs that have [[strong orientation]]s are exactly the [[k-edge-connected graph|2-edge-connected graphs]]. That is, it is possible to choose a direction for each edge of an undirected graph {{mvar|G}}, turning into a [[directed graph]] that has a path from every vertex to every other vertex, if and only if {{mvar|G}} is [[connected graph|connected]] and has no [[Bridge (graph theory)|bridge]].