A span map has four sites of odd degree: what does that force on an inspection plan covering every span?

## Where the obstruction comes from A route that never reuses a span consumes span-ends at each site in pairs — one arriving, one departing — except at its two endpoints, which are unpaired once each. So along any single such route, **at most two sites can have odd degree**: its start and its finish. Four odd-degree sites therefore cannot be covered by one route, whatever order you try, and no amount of clever starting-point selection changes that. This is a parity obstruction, not a search failure. It is decided by counting, before any routing work is done. ## Counting the routes you need Let the map be connected with `2k` sites of odd degree, `k` at least one. Two arguments meet in the middle: 1. **Lower bound.** Each route absorbs at most two odd sites as its endpoints, and every odd site must be an endpoint of some route in the plan. So the plan needs at least `k` routes. 2. **Upper bound.** Pair the `2k` odd sites arbitrarily and imagine adding `k` temporary spans, one per pair. Every degree is now even and the map is still connected, so one closed route covers everything. Delete the `k` temporary spans again: the closed route falls apart into exactly `k` open routes. The minimum is therefore exactly `k`, half the odd count. For the map in the question, `2k = 4`, so `k = 2` — two routes, no more and no fewer. | sites of odd degree | fewest routes, each span exactly once | shape of the plan | |---|---|---| | 0 | 1 | one closed route returning to base | | 2 | 1 | one open route, pinned to the two odd sites | | 4 | 2 | two open routes, each ending at two odd sites | | 6 | 3 | three open routes | The count of odd-degree sites is always even, so the table never needs a row for an odd count. ## Or pay to change the parity instead If a single crew or a single closed circuit is what the plan actually needs, you can attack the graph rather than the schedule. Choose two routes through the map, each joining one pair of odd sites, and **duplicate** the spans along them — that is, plan to traverse those spans twice. - Each duplicated span adds one to the degree at both of its ends. - At an interior site of such a route, two duplicated spans meet, so its degree rises by two and its parity is unchanged. - At each of the four odd sites exactly one duplicated span lands, so its degree rises by one and its parity flips to even. Every degree is now even and the map is connected, so one closed route covers every span, revisiting only the duplicated ones. The cost is the total length of the two pairing routes, which is why the sensible choice is the **shortest** pairing rather than an arbitrary one. ## The trade the plan is really making Both options are legitimate, and they spend different budgets: - **More routes**: two crews, or one crew on two days, with no span walked twice; the plan finishes in one pass each but needs a second mobilisation and two start-and-end locations that are dictated by the odd sites, not chosen. - **More distance**: one closed route that returns to base, at the price of re-walking the duplicated spans; scheduling is simpler, total distance is higher. The choice depends on whether mobilisation or distance dominates, and the graph gives you the exact trade rather than a guess: `k` routes, or the extra distance of the cheapest pairing of the odd sites. ## The errors this catches - **"Start at an odd site and it works out."** True when exactly two sites are odd; false here, because one route has only two endpoints and there are four odd sites to serve. - **"One route per odd site."** That double-counts: each route takes care of two odd sites, so four odd sites need two routes, not four. - **"Add one temporary span."** One extra span fixes only one pair; two odd sites would remain, leaving an open route rather than a closed one — fine if an open route is acceptable, but it is not the same answer. - **"Just skip the awkward spans."** The requirement was coverage of every span; dropping a span changes the problem rather than solving it. The pleasant part of this material is how little work the decision takes. Counting odd-degree sites is a single pass over the map, and it produces the number of passes, where each must begin and end, and what the alternative costs — before anyone plans a route at all.