Eulerian digraph
E824091
An Eulerian digraph is a directed graph in which every vertex has equal in-degree and out-degree, allowing for a closed trail that traverses each edge exactly once.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Eulerian digraph canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T9838903 — 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: Eulerian digraph Context triple: [de Bruijn–van Aardenne–Ehrenfest theorem, concernsProperty, Eulerian digraph]
-
A.
Eulerian trail
An Eulerian trail is a path in a graph that traverses every edge exactly once, possibly revisiting vertices.
-
B.
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.
-
C.
DAG
DAG is the National Rail station code for Dalgety Bay railway station in Fife, Scotland.
-
D.
Euler’s theorem
Euler’s theorem is a fundamental result in number theory stating that for any integer a coprime to n, a raised to the power of φ(n) is congruent to 1 modulo n.
-
E.
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.
- 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: Eulerian digraph Target entity description: An Eulerian digraph is a directed graph in which every vertex has equal in-degree and out-degree, allowing for a closed trail that traverses each edge exactly once.
-
A.
Eulerian trail
An Eulerian trail is a path in a graph that traverses every edge exactly once, possibly revisiting vertices.
-
B.
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.
-
C.
DAG
DAG is the National Rail station code for Dalgety Bay railway station in Fife, Scotland.
-
D.
Euler’s theorem
Euler’s theorem is a fundamental result in number theory stating that for any integer a coprime to n, a raised to the power of φ(n) is congruent to 1 modulo n.
-
E.
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.
- F. None of above. chosen
Statements (45)
| Predicate | Object |
|---|---|
| instanceOf |
directed graph
ⓘ
graph theory concept ⓘ |
| contrastsWith | Hamiltonian digraph ⓘ |
| decisionProblemComplexity | linear time in number of vertices plus edges ⓘ |
| definedOn | directed multigraphs (possibly with parallel arcs) ⓘ |
| equivalentTo |
directed graph with a closed Eulerian trail
ⓘ
directed graph with an Eulerian circuit ⓘ |
| generalizes | Eulerian graph (undirected) ⓘ |
| hasAlgorithm |
Fleury’s algorithm adapted to directed graphs
ⓘ
linked to:
Fleury's algorithm
Hierholzer’s algorithm to find an Eulerian circuit ⓘ
linked to:
Hierholzer's algorithm
|
| hasDecisionProblem | testing whether a given digraph is Eulerian ⓘ |
| hasEdgeTraversal |
Eulerian circuit starts and ends at the same vertex
ⓘ
Eulerian circuit traverses each directed edge exactly once ⓘ |
| hasGlobalCondition | strong connectivity of non-isolated vertices ⓘ |
| hasHistoricalOrigin | generalization of Euler’s Königsberg bridges problem to directed graphs ⓘ |
| hasLocalCondition | balance of flow at each vertex ⓘ |
| hasNecessaryAndSufficientCondition | strongly connected after removing zero-degree vertices and in-degree(v)=out-degree(v) for all v ⓘ |
| hasProperty |
admits a closed trail using each edge exactly once
ⓘ
admits an Eulerian circuit ⓘ any Eulerian circuit induces a cyclic ordering of incident edges at each vertex ⓘ any Eulerian digraph is balanced at every vertex ⓘ any strongly connected balanced digraph is Eulerian ⓘ edge set can be partitioned into directed cycles ⓘ every edge lies on some Eulerian trail ⓘ every vertex has equal in-degree and out-degree ⓘ removing edges of an Eulerian circuit leaves a union of Eulerian digraphs (possibly empty) ⓘ |
| implies |
every vertex has even degree in the underlying undirected graph
ⓘ
existence of a decomposition of edges into directed cycles ⓘ |
| mayAllow | loops ⓘ |
| relatedTo |
Eulerian circuit
ⓘ
Eulerian trail ⓘ semi-Eulerian digraph ⓘ |
| requiresCondition |
each vertex with nonzero degree lies in a single strongly connected component of the underlying digraph
ⓘ
every vertex with nonzero degree belongs to the same weakly connected component ⓘ in-degree(v) = out-degree(v) for every vertex v ⓘ underlying undirected graph is connected when ignoring isolated vertices ⓘ |
| studiedIn |
Eulerian graph theory
ⓘ
algorithmic graph theory ⓘ |
| usedFor |
designing closed walk tours in directed networks
ⓘ
modeling conservation laws in flow networks ⓘ |
| usedIn |
DNA sequencing by Eulerian paths
ⓘ
circuit design ⓘ network routing ⓘ postman problems ⓘ route planning problems ⓘ |
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: Eulerian digraph Description of subject: An Eulerian digraph is a directed graph in which every vertex has equal in-degree and out-degree, allowing for a closed trail that traverses each edge exactly once.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.