skip to content

In a fibre network, when can one closed route use every span exactly once?

level: middleimportance: must knowfreq 58%

answer

  1. every span once, not every site
  2. in and out, so pairs
  3. count the odd-degree sites
  4. parity alone is not enough
  5. zero odd closes, two odd opens

basics

~20 s

Exactly when every span lies in one connected piece and every site has even degree. Each visit to a site uses one span in and one out, so an odd degree makes a closed route over every span impossible.

solid answer

~40 s

A route that uses every span exactly once is a **trail** containing every edge; closed, it is an **Euler circuit**. The condition has two halves and both are needed. First, parity: every time the route reaches a site it must leave along a different unused span, so span-ends at each site are consumed in pairs, which forces **every degree to be even**. Second, connectivity: all spans must lie in one connected piece, otherwise no single route can reach both pieces — sites with no spans at all are irrelevant. Together these are also sufficient. If exactly two sites have odd degree you instead get an **Euler trail**, an open route that must start at one odd site and end at the other; with four or more odd sites, no single route exists.

code

pseudocode · 13 lines
pseudocode
odd = 0
for each site v in the network:
    if degree(v) is odd:
        odd = odd + 1

if the spans do not all lie in one connected piece:
    answer "no single route"
else if odd = 0:
    answer "closed route exists"
else if odd = 2:
    answer "open route exists, between the two odd sites"
else:
    answer "no single route"

go deeper

for a junior

Recall the count that decides it: all degrees even and the spans in one piece means a closed route exists; exactly two odd means an open one.

for a middle

Explain why parity is forced — an arrival and a departure consume two different span-ends — and why connectivity is a second requirement, with the two-rings counterexample.

for a senior

Use the count as a diagnosis on a real map: say how many passes the plan needs, where each must begin and end, and what to change to reach one pass.

for a principal

Treat the parity count as a cheap design constraint: it tells you before any scheduling work whether one crew can cover the network or whether the topology forces extra passes.

## The vocabulary the question turns on Four words get confused constantly, and the Euler condition is about one of them: - a **walk** is any sequence of sites where consecutive ones are joined by a span — it may repeat sites and spans freely; - a **trail** is a walk that never repeats a **span**, though it may revisit sites; - a **path** is a walk that repeats nothing at all; - a **cycle** is a closed path: it returns to its start and repeats nothing else. "Use every span exactly once" therefore asks for a trail containing every edge. Closed, that is an **Euler circuit**; allowed to end elsewhere, it is an **Euler trail**. Note what is *not* being asked: visiting every **site** once is a different problem about vertices, and it has no comparable local test — its difficulty belongs to complexity theory, not here. ## Why parity is forced Walk the route and watch one site. Every arrival consumes one span-end, and because the route may not reuse a span, the departure must consume a **different** unused span-end. Arrivals and departures therefore pair up the span-ends at that site. - For an interior site, every pairing is arrival-then-departure, so its span-ends are consumed two at a time: its degree is even. - For a **closed** route the base site is no exception — the first departure pairs with the final arrival — so every site without exception must have even degree. - For an **open** route the two endpoints are unpaired once each, so exactly those two sites may have odd degree. This argument gives **necessity** only: it says an odd degree rules a route out. It does not by itself say that even degrees buy you one. ## Connectivity is the second, separate requirement Take two rings of fibre that share no site. Every site has degree two, so every degree is even — and yet no single route covers both rings, because nothing joins them. The missing condition is that **all spans lie in one connected piece**. Sites with no spans at all can be ignored: the route never needs to reach them. With both halves in place the condition becomes **sufficient**, and constructively so. Start anywhere and keep walking along unused spans; parity guarantees you can always leave a site you have just entered, so you can only get stuck back at the start, closing a sub-tour. If unused spans remain, connectivity guarantees some site on the tour still touches one; start a second sub-tour there and splice it into the first. Repeat until nothing is left. ## The decision table | sites of odd degree | one closed route over every span? | one open route over every span? | |---|---|---| | 0 | yes — an Euler circuit | not needed; the circuit already covers everything | | 2 | no | yes, and it must start at one odd site and end at the other | | 4 or more | no | no | The table has no row for an odd *count* of odd-degree sites, because that cannot happen: degree-sum reasoning makes odd-degree sites come in pairs. Notice also why the open route's endpoints are not a free choice — an odd site can only ever be an endpoint, so with two of them the route is pinned at both ends. ## The traps this question is set to catch 1. **Even degrees alone.** Stating the parity half and forgetting connectivity is the most common miss, and the two-rings example is the interviewer's follow-up. 2. **Requiring degree two.** A ring satisfies the condition, but so does a site with six spans; the condition is parity, not a fixed degree. 3. **Sites versus spans.** "Every span exactly once" and "every site exactly once" are different problems with completely different answers. 4. **Direction of the claim.** Even degree is necessary for a closed route; even degree **plus** connectivity is what makes it sufficient. Stating either half as the whole test is wrong in a way that shows. ## Why an engineer meets it The shape recurs whenever every *link* must be exercised once: an inspection round that must traverse each span, a test plan that must exercise each transition of a state machine exactly once, a maintenance sweep that must physically walk each segment. The valuable part is not the theorem name but the diagnosis it gives for free — count the odd-degree sites, and you know immediately whether one pass can do it, whether you need to start and finish in different places, or whether you must buy a second pass. That count is cheap, local and decisive.

  • How does the answer change when the route need not return to base?
    Then you need an Euler trail: the spans still have to lie in one connected piece, but exactly two sites may have odd degree, and the route is forced to start at one of them and end at the other. An odd site can only ever be an endpoint, so both ends are pinned.
  • What if some sites have no spans at all?
    They are irrelevant. The requirement is that all spans lie in one connected piece; an isolated site holds no span the route must cover, so it may be ignored. That is why the condition is usually stated as connected after discarding degree-zero sites.
  • Does this tell you anything about visiting every site exactly once?
    No. That is a question about vertices rather than edges, and no local degree test decides it — the two problems only look alike. Answering the site version with the parity rule is a standard error.

saying these in an interview costs you the question

  • Saying every site must have degree exactly two
  • Treating even degrees as sufficient without checking connectivity
  • Requiring the route to visit every site once instead
  • Believing a route can start at an odd site and still close the loop
  • Counting spans rather than site degrees to decide