Eulerian trail
E467732
An Eulerian trail is a path in a graph that traverses every edge exactly once, possibly revisiting vertices.
All labels observed (4)
| Label | Occurrences |
|---|---|
| Eulerian trail canonical | 3 |
| Eulerian path | 2 |
| Eulerian circuit | 1 |
| Eulerian cycle | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T4764112 — 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 trail Context triple: [Seven Bridges of Königsberg problem, hasConcept, Eulerian trail]
-
A.
Red Dot Trail
Red Dot Trail is a popular marked hiking route within Massachusetts' Blue Hills Reservation, known for its scenic views and varied terrain.
-
B.
Jeju Olle Trail
Jeju Olle Trail is a network of scenic walking paths that circle South Korea’s Jeju Island, showcasing its coastal landscapes, rural villages, and volcanic terrain.
-
C.
Gotemba Trail
Gotemba Trail is one of the main climbing routes on Japan’s Mount Fuji, known for its long, less crowded ascent across expansive volcanic ash slopes.
-
D.
Nikoloz Romanov Trail
Nikoloz Romanov Trail is a popular long-distance hiking route in Georgia’s Borjomi-Kharagauli National Park, known for its scenic mountain landscapes and diverse forest ecosystems.
-
E.
Xiaoyoukeng Trail
Xiaoyoukeng Trail is a popular hiking path in Taiwan’s Yangmingshan National Park known for its volcanic fumaroles, sulfur vents, and scenic mountain views.
- 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 trail Target entity description: An Eulerian trail is a path in a graph that traverses every edge exactly once, possibly revisiting vertices.
-
A.
Red Dot Trail
Red Dot Trail is a popular marked hiking route within Massachusetts' Blue Hills Reservation, known for its scenic views and varied terrain.
-
B.
Jeju Olle Trail
Jeju Olle Trail is a network of scenic walking paths that circle South Korea’s Jeju Island, showcasing its coastal landscapes, rural villages, and volcanic terrain.
-
C.
Gotemba Trail
Gotemba Trail is one of the main climbing routes on Japan’s Mount Fuji, known for its long, less crowded ascent across expansive volcanic ash slopes.
-
D.
Nikoloz Romanov Trail
Nikoloz Romanov Trail is a popular long-distance hiking route in Georgia’s Borjomi-Kharagauli National Park, known for its scenic mountain landscapes and diverse forest ecosystems.
-
E.
Xiaoyoukeng Trail
Xiaoyoukeng Trail is a popular hiking path in Taiwan’s Yangmingshan National Park known for its volcanic fumaroles, sulfur vents, and scenic mountain views.
- F. None of above. chosen
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
graph theory concept
ⓘ
trail in a graph ⓘ |
| algorithmicConstruction |
Fleury's algorithm
ⓘ
Hierholzer's algorithm ⓘ |
| allowsEdgeRepetition | false ⓘ |
| allowsVertexRepetition | true ⓘ |
| alsoKnownAs |
Eulerian path
ⓘ
linked to:
Eulerian trail
|
| complexityDecisionProblem | decidable in linear time in the size of the graph ⓘ |
| contrastWith | Hamiltonian path ⓘ |
| definition | a trail in a graph that traverses every edge exactly once ⓘ |
| differenceFromHamiltonianPath | covers edges instead of vertices ⓘ |
| edgeCoverage | uses every edge of the graph ⓘ |
| edgeMultiplicity | each edge appears at most once in the trail ⓘ |
| endVertexConditionUndirected | if graph has two odd-degree vertices, trail ends at the other odd-degree vertex ⓘ |
| existenceConditionDirectedGraph |
one vertex may have out-degree = in-degree + 1 and one vertex may have in-degree = out-degree + 1
ⓘ
underlying undirected graph is connected (ignoring isolated vertices) and in-degree equals out-degree for all vertices except possibly two ⓘ |
| existenceConditionUndirectedGraph | graph has exactly zero or two vertices of odd degree and all non-isolated vertices lie in a single connected component ⓘ |
| field | graph theory ⓘ |
| generalizationOf | Eulerian circuit ⓘ |
| graphType |
can be defined for directed graphs
ⓘ
can be defined for multigraphs ⓘ can be defined for undirected graphs ⓘ |
| hasEulerianCircuitConditionDirected | in-degree equals out-degree for every vertex and all vertices with nonzero degree lie in a single strongly connected component of the underlying graph ⓘ |
| hasEulerianCircuitConditionUndirected | all vertices with nonzero degree have even degree and lie in a single connected component ⓘ |
| implies | graph is connected in the subgraph induced by edges of the trail ⓘ |
| introducedBy | Leonhard Euler ⓘ |
| mathematicalArea | discrete mathematics ⓘ |
| mayStartAndEndAtDifferentVertices | true ⓘ |
| mayStartAndEndAtSameVertex | true ⓘ |
| namedAfter | Leonhard Euler ⓘ |
| property | provides necessary and sufficient degree conditions for existence in finite graphs ⓘ |
| relatedProblem |
Seven Bridges of Königsberg
ⓘ
linked to:
Seven Bridges of Königsberg problem
|
| requiresConnectivityDirected | underlying undirected graph of non-isolated vertices is connected ⓘ |
| requiresConnectivityUndirected | all vertices with nonzero degree belong to a single connected component ⓘ |
| specialCaseOf |
trail in a graph
ⓘ
walk in a graph ⓘ |
| startEndConditionDirected | if in-degree equals out-degree for all vertices, trail can start and end at the same vertex ⓘ |
| startEndConditionUndirected | if all vertices have even degree, trail can start and end at the same vertex ⓘ |
| startVertexConditionUndirected | if graph has two odd-degree vertices, trail starts at one of them ⓘ |
| topicOf | introductory graph theory courses ⓘ |
| traversesEveryEdge | exactly once ⓘ |
| usedIn |
Chinese postman problem
ⓘ
DNA sequencing by Eulerian methods ⓘ circuit board routing ⓘ network routing ⓘ route inspection problem ⓘ |
| vertexCoverage | may not visit every vertex ⓘ |
| vertexMultiplicity | vertices may appear multiple times in the trail ⓘ |
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 trail Description of subject: An Eulerian trail is a path in a graph that traverses every edge exactly once, possibly revisiting vertices.
Referenced by (7)
Full triples — surface form annotated when it differs from this entity's canonical label.
linked to: Eulerian trail
linked to: Eulerian trail
subject linked to:
Hamiltonian cycle concept
linked to: Eulerian trail
linked to: Eulerian trail