Robbins theorem
E1015500
Robbins theorem is a result in graph theory that characterizes when a connected graph can be oriented to become strongly connected, providing a key condition for the existence of strongly connected orientations.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Robbins theorem canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T13012660 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Robbins theorem Context triple: [Herbert Robbins, knownFor, Robbins theorem]
-
A.
Turán's theorem
Turán's theorem is a fundamental result in extremal graph theory that determines the maximum number of edges a graph can have without containing a complete subgraph of a given size.
-
B.
Menger theorem in graph theory
Menger's theorem in graph theory is a fundamental result that characterizes the connectivity between two vertices in a graph by equating the maximum number of pairwise internally disjoint paths between them with the minimum size of a vertex cut separating them.
-
C.
Erdős–Gallai theorem
The Erdős–Gallai theorem is a fundamental result in graph theory that characterizes which sequences of nonnegative integers can occur as the degree sequences of simple graphs.
-
D.
Graham–Rothschild theorem
The Graham–Rothschild theorem is a fundamental result in Ramsey theory that generalizes classical partition theorems to higher-dimensional combinatorial structures.
-
E.
Graham–Pollak theorem
The Graham–Pollak theorem is a result in graph theory that states the edges of a complete graph on n vertices cannot be partitioned into fewer than n−1 complete bipartite subgraphs.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Robbins theorem Target entity description: Robbins theorem is a result in graph theory that characterizes when a connected graph can be oriented to become strongly connected, providing a key condition for the existence of strongly connected orientations.
-
A.
Turán's theorem
Turán's theorem is a fundamental result in extremal graph theory that determines the maximum number of edges a graph can have without containing a complete subgraph of a given size.
-
B.
Menger theorem in graph theory
Menger's theorem in graph theory is a fundamental result that characterizes the connectivity between two vertices in a graph by equating the maximum number of pairwise internally disjoint paths between them with the minimum size of a vertex cut separating them.
-
C.
Erdős–Gallai theorem
The Erdős–Gallai theorem is a fundamental result in graph theory that characterizes which sequences of nonnegative integers can occur as the degree sequences of simple graphs.
-
D.
Graham–Rothschild theorem
The Graham–Rothschild theorem is a fundamental result in Ramsey theory that generalizes classical partition theorems to higher-dimensional combinatorial structures.
-
E.
Graham–Pollak theorem
The Graham–Pollak theorem is a result in graph theory that states the edges of a complete graph on n vertices cannot be partitioned into fewer than n−1 complete bipartite subgraphs.
- F. None of above. chosen
Statements (44)
| Predicate | Object |
|---|---|
| instanceOf |
result in graph theory
ⓘ
theorem ⓘ |
| appliesTo | finite undirected graphs ⓘ |
| assumes |
graph is connected
ⓘ
graph is finite ⓘ graph is undirected ⓘ |
| category |
theorems about connectivity
ⓘ
theorems in graph theory ⓘ |
| characterizes | when a connected graph admits a strongly connected orientation ⓘ |
| conclusion | there exists an orientation of every edge such that the resulting digraph is strongly connected ⓘ |
| conditionType | necessary and sufficient condition ⓘ |
| equivalentFormulation | A connected undirected graph has a strongly connected orientation if and only if it is 2-edge-connected ⓘ |
| field | graph theory ⓘ |
| generalizationOf | characterizations of strongly connected orientations of graphs ⓘ |
| hasApplication |
communication networks
ⓘ
network design ⓘ reliability of network connectivity ⓘ transportation networks ⓘ |
| implies |
every 2-edge-connected graph has a strongly connected orientation
ⓘ
if a connected graph has a bridge then it has no strongly connected orientation ⓘ |
| importance | fundamental result in graph orientation theory ⓘ |
| involvesObject |
directed graph
ⓘ
strongly connected digraph ⓘ undirected graph ⓘ |
| involvesProperty |
absence of bridges
ⓘ
edge-connectivity at least 2 ⓘ |
| namedAfter |
Herbert E. Robbins
ⓘ
linked to:
Herbert Robbins
|
| originalAuthor |
Herbert E. Robbins
ⓘ
linked to:
Herbert Robbins
|
| proofTechnique | graph-theoretic arguments ⓘ |
| publicationTitle | A theorem on graphs with an application to a problem of traffic control ⓘ |
| publicationYear | 1939 ⓘ |
| publishedIn | American Mathematical Monthly ⓘ |
| relatedTo |
Menger theorem
ⓘ
linked to:
Menger theorem in graph theory
edge-connectivity ⓘ graph orientation ⓘ strong connectivity ⓘ |
| states | A connected undirected graph has a strongly connected orientation if and only if it has no bridges ⓘ |
| status | proven ⓘ |
| usedFor | deciding existence of strongly connected orientations ⓘ |
| usesConcept |
2-edge-connected graph
ⓘ
bridge ⓘ connected graph ⓘ cut edge ⓘ strongly connected orientation ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Robbins theorem Description of subject: Robbins theorem is a result in graph theory that characterizes when a connected graph can be oriented to become strongly connected, providing a key condition for the existence of strongly connected orientations.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.