22The数漫encaseThebridges of Konigsberg (anno1736)Fig.1.8.1.Conversely, let G be a connected graph with all degrees even, andletW= voeo...et-1vebe a longest walk in G usingno edge more than once.Since W cannotbe extended, it already contains all the edges at ve. By assumption, thenumber of such edges is even. Hence ve = vo, so W is a closed walkSuppose W is not an Euler tour. Then G has an edge e outside Wbut incident with a vertex of W, say e = ww. (Here we use the connect-edness of G.asintheproof of Proposition1.4.1.)Then thewalkueviei...e-iveeo..ei-ui口is longer than W, a contradiction.Fig.1.8.2.A graph formalizing the bridge problem22 1. The Basics Fig. 1.8.1. The bridges of K¨onigsberg (anno 1736) Conversely, let G be a connected graph with all degrees even, and let W = v0e0 ...e
−1v
be a longest walk in G using no edge more than once. Since W cannot be extended, it already contains all the edges at v
. By assumption, the number of such edges is even. Hence v
= v0, so W is a closed walk. Suppose W is not an Euler tour. Then G has an edge e outside W but incident with a vertex of W, say e = uvi. (Here we use the connect￾edness of G, as in the proof of Proposition 1.4.1.) Then the walk ueviei ...e
−1v
e0 ...ei−1vi is longer than W, a contradiction.
Fig. 1.8.2. A graph formalizing the bridge problem