Motivation
A route that uses every edge once solves a different problem from a route that visits every vertex once. Repeated vertices are natural when the objects to enumerate are transitions or overlapping words. Euler traversal turns that edge requirement into degree balance and a connectivity condition.
For words, the graph vertices represent a remembered prefix of fixed length, and each edge represents one complete block to be listed. Traversing every edge once makes every block occur once. The graph's overlap rule translates a circuit into one compact cyclic word rather than a disconnected list of blocks.
Definitions
Definition 5.2.1
(Directed trails, degrees and weak connectivity)
Let a finite directed multigraph have at least one vertex and labeled arcs, allowing loops and parallel arcs. A trail does not repeat an arc. A closed Euler trail starts and ends at the same vertex and uses every arc once. An open Euler trail with distinct endpoints starts at and ends at and also uses every arc once.
A loop contributes one to both indegree and outdegree. Weak connectivity on the nonisolated vertices means that, after ignoring directions and isolated vertices, those vertices form one connected graph when any arcs exist. An edgeless graph has the empty closed trail at any chosen vertex.
Definition 5.2.2
(Universal words and the word-overlap graph)
Fix an alphabet of size and a block length . A cyclic word of positive length is read periodically; its length- blocks may wrap around the end, even more than once if . A universal cyclic word contains every member of . We seek one where each occurs exactly once.
A linear word has no wrapping. If its length is , it has starting positions for length- blocks. The word-overlap graph has vertices and one labeled arc per word in , directed from its length- prefix to its length- suffix. For there is one empty-word vertex and labeled loops.
Concept lensStructural
Vertices store overlap memory; edges are the objects that must appear once
A repeated vertex means a remembered suffix is revisited, which is harmless. Repeating an edge would repeat its whole block, which is forbidden in the desired universal word. The degree-balance theorem controls that edge enumeration while the overlap relation compresses it into one cyclic sequence.
Theorem/Proposition
Theorem 5.2.3
(Balance and nonisolated connectivity characterize Euler trails)
A finite directed multigraph has a closed Euler trail exactly when all vertices have equal indegree and outdegree and its nonisolated underlying graph is connected whenever arcs exist.
For distinct , an open Euler trail from to exists exactly when that same connectivity condition holds, has outdegree one greater than indegree, has indegree one greater than outdegree, and all other vertices are balanced.
Theorem 5.2.4
(Universal words attain both counting lower bounds)
For every , there is a cyclic word of length in which every length- word occurs exactly once. No universal cyclic word can be shorter.
There is also a linear word of length containing each length- word exactly once, and no shorter linear universal word exists. The cyclic definition includes the one-symbol alphabet even when the requested block is longer than the whole cycle.
Theorem 5.2.5
(The construction is linear in its explicit graph)
Given adjacency lists with persistent unused-arc pointers, Euler cycle splicing can be implemented in graph operations and stored entries. For the overlap graph these counts are and .
For a fixed alphabet, a straightforward implementation with explicit word labels uses symbol work and storage, including graph construction and the initial linear-word prefix. For , the output size itself is exponential in ; this is not a polynomial-in-block-length output claim.
Proof sketch or proof idea
Proof
(Degree counting, greedy closed fragments and splicing)
Necessity of the closed criterion follows by counting arrivals and departures of the trail at every vertex. Its used arcs also connect every nonisolated vertex in the underlying sense. The open degree differences follow from the one initial departure and final arrival; every other arrival is paired with a departure.
For closed sufficiency, start at a vertex with an unused outgoing arc and follow unused arcs greedily. If a trail beginning at stopped at a different vertex , the used incoming count there would exceed the used outgoing count by one. With no unused outgoing arc, that would exceed the original incoming count as well, contradicting original balance. Thus the finite greedy trail can stop only back at its start, producing a closed trail.
Removing the used arcs of a closed trail preserves balance in the remaining graph. If any vertex on the current trail has unused outgoing arcs, repeat the argument there to create another closed trail and splice it into the old one at that vertex. Arc labels prevent reuse even when several arcs have identical endpoints.
When no such vertex remains, all arcs must have been used. Otherwise weak connectivity supplies an unused arc crossing between a vertex already on the trail and one outside it, by taking the first boundary crossing of an underlying path. A used crossing would already have put both endpoints on the trail. If the unused crossing points outward, it directly supplies an unused outgoing arc on the trail. If it points inward, residual balance at its endpoint supplies an unused outgoing arc there too. Both contradict the stopping condition. This proves sufficiency without replacing weak connectivity by an unproved stronger hypothesis.
For the open case, add one distinguished auxiliary arc . It balances the endpoints and preserves nonisolated connectivity. A closed Euler trail exists in the augmented graph. Rotate its arc list to begin immediately after the auxiliary arc and then remove that arc; the remaining list is an open Euler trail from to . The distinguished label makes this valid even if another arc already has the same direction and endpoints.
Proof X-ray
Residual balance prevents a greedy fragment from ending at the wrong vertex
The sufficiency proof uses its two hypotheses in two different places. Balance is used locally, at the moment a greedy walk stops: a walk that started at and is stuck at has used one more arc into than out of it, and with no unused outgoing arc left, must originally have had fewer outgoing than incoming arcs. The same count works in every later round, because a closed fragment uses equally many arcs into and out of each vertex, so the residual graph is again balanced.
Connectivity is used only once, globally, after the splicing has stopped: it produces a crossing arc between the tour's vertex set and the rest, and residual balance at the crossing's endpoint on the tour turns an inward crossing into an unused outgoing arc. Neither hypothesis can do the other's job: two loops at two separate vertices are balanced but cannot be joined, while a single arc is connected but strands the walk at . The open case is reduced to the closed case by one labeled auxiliary arc, so no third argument is needed.
Implement the splices without repeatedly rescanning the whole tour
Proof
(Pointer and worklist accounting)
Keep outgoing adjacency pointers and a circular linked list of tour occurrences. A greedy fragment advances an outgoing pointer whenever it uses an arc. Store a known tour occurrence for each visited vertex so a new closed fragment can be inserted there by a constant number of pointer changes.
Maintain a worklist of candidate occurrences whose vertices may still have unused outgoing arcs. When a new fragment creates occurrences, inspect and schedule them; when an old candidate is removed from the worklist, skip it if its outgoing list is exhausted. A starting vertex with still more unused arcs occurs in the newly created fragment too, so it can be scheduled again through that new occurrence.
Each arc creates only constant many stored tour items and is processed once by an adjacency pointer. Each occurrence is scheduled only when created, and each scheduled candidate is removed once. The initial vertex scan, adjacency work, worklist and splices consequently take operations. A naive implementation that rescanned the entire growing tour after every fragment would not inherit that bound; the worklist accounting is part of the implementation.
The overlap graph satisfies the criterion
Proof
(Degrees and strong connectivity of the overlap graph)
At any length- vertex, appending any alphabet symbol gives one outgoing arc, and prepending any symbol gives one incoming arc. Both degrees are , including the empty-word vertex when .
The graph is strongly connected and hence weakly connected: from any vertex, append the symbols of a desired target vertex in order. After steps, the remembered suffix is exactly that target. At no steps are needed, since there is only one vertex. Therefore the proved Euler criterion gives a circuit containing all labeled block arcs once.
Overlap converts the circuit into one word
Proof
(Reading the circuit as a word, lower bounds and symbol cost)
Read a linear representation by writing the initial vertex word and then the last symbol of each arc in circuit order. Inductively, the length- block ending at each newly written symbol is exactly that arc's label: the prior suffix is its tail vertex, and the append operation gives the whole edge word. There are such blocks, all distinct and exhaustive. The total length is .
For a cyclic representation, read the last symbols of the arcs around the circuit. Every block ending at an arc position is its label, because successive arc labels overlap in their last/first symbols, including the last-to-first closure. Following the preceding arcs backward justifies this for all symbols, even when that means wrapping more than once. Shifting from block-ending positions to block-starting positions permutes the cycle positions, so every block still appears once.
Any cyclic word of length has only block-starting positions, hence must have to contain all the different blocks. A linear universal word must first have length at least , and then . These are the two lower bounds, both attained by the circuit construction.
For explicit word-labeled graph construction over a fixed alphabet, store all length- vertices in a trie. Each arc and its shifted head can be written and located using symbol operations; enumerating all arcs therefore uses . The Euler phase uses the stated graph-entry model. This explicit symbol bound does not treat arbitrarily long word labels as one free comparison or assume a constant-time string dictionary without accounting for it.
Worked examples
Worked example 5.2.6
(Eight binary three-blocks fit in an eight-symbol cycle)
The cyclic word has consecutive wrapped three-blocks
These are all eight binary words of length three. In the overlap graph they give the closed vertex route . Each of the four two-bit vertices has indegree and outdegree two, and every block arc appears once.
A linear representative is , appending the initial two symbols for the final wrapped blocks. Its ten symbols give exactly eight ordinary three-block positions, meeting the linear lower bound as well.
Worked example 5.2.7
(A loop fragment is spliced into a larger circuit)
Use arcs consisting of a loop at , an arc and an arc . Both vertices are balanced. The loop alone is a valid initial closed fragment at .
The remaining two arcs form the closed fragment , which can be spliced at that occurrence of , yielding or the corresponding cyclic rotation. Every arc is used once although occurs repeatedly. The loop is a distinct arc and contributes one incoming and one outgoing incidence, rather than being discarded as irrelevant.
Worked example 5.2.8
(A one-symbol alphabet requires repeated wrapping, not a longer cycle)
For alphabet and block length four, the only block is . The one-symbol cycle contains it at its sole starting position by periodic reading, wrapping several times. The overlap graph has the single vertex and the single loop labeled .
The shortest linear word is instead , of length four, as the formula predicts. At block length one with alphabet , the graph is one empty-word vertex with three loops, and the cycle contains each one-symbol block once. These two boundary cases use the same definitions.
Common mistakes
Counterexample mode
Balanced degrees alone cannot join disconnected fragments
Take two vertices, each with its own loop and no arc between them. Every indegree equals its outdegree, but no single trail can use both loops. The nonisolated underlying graph is disconnected. This is why connectivity is a separate hypothesis, rather than something inferred from degree balance.
Common mistake
(An Euler trail may repeat vertices)
Do not confuse an Euler trail with a path that cannot repeat vertices. In the overlap graph for binary three-blocks, the circuit passes through each of the four vertices twice; only the arcs are used exactly once.
Common mistake
(Wrapped and unwrapped block counts)
Cyclic block counts include wrapping, while linear counts include only starts with enough remaining symbols. The eight-symbol cycle contains all binary three-blocks, but read as a linear word it has only six three-block positions; the linear representative needs two more symbols.
Common mistake
(Linear in the graph is not polynomial in the block length)
A linear graph-operation bound does not make an exponentially long universal word polynomial in its short length parameter. For and the cycle has symbols, and any algorithm that writes it out spends at least that many steps.
Summary
Directed degree balance and nonisolated weak connectivity give complete Euler trail criteria. Residual balance supports closed-fragment splicing, and persistent pointers plus scheduled occurrences give linear graph work. Word-overlap graphs satisfy those conditions, producing optimal cyclic and linear universal words with short-cycle and empty-prefix boundaries treated explicitly.
Exercises
Quick check
(Verify that the cyclic word contains all ordered pairs over the alphabet exactly once. Prove its length is minimal.)
List its nine cyclic pair starts, including the last-to-first pair.
Solution · Answer
The pairs are . Each of the nine possible ordered pairs occurs once. Any cyclic word containing them all has at least nine starting positions and therefore length at least nine. The displayed word attains this lower bound, with its last pair using the final two followed by the initial zero.
Quick check
(Why must a binary linear word containing every three-bit block have at least ten symbols? Give a word attaining the bound.)
Count ordinary starting positions and compare with the eight possible blocks.
Solution · Answer
A linear word of length has three-block positions. Containing all eight different blocks requires , hence . The word attains ten, with its blocks listed in the first example. An eight-symbol cycle is sufficient only because its wrapped blocks are also allowed; dropping that convention changes the count.
Quick check
(Find an open Euler trail for arcs , , and a loop at . Verify endpoint degrees and explain the auxiliary-arc construction.)
Keep the loop as one of the four labeled arcs.
Solution
Vertex has outdegree two and indegree one; has indegree two and outdegree one; is balanced. The nonisolated underlying graph is connected. The arc sequence uses all four arcs and has the required endpoints.
Adding an auxiliary arc makes every vertex balanced. The corresponding closed trail can be rotated to place that arc last, and deleting it recovers the displayed open trail. Its special label distinguishes it from any original parallel arc that might also be present.