, a network is a number of point
s, with line segment
s connecting them. The number of points, line segments (called "paths"), and region
s (how many "spaces" within the network, including the exterior
-- a square
has 2 regions, a square divided into two triangle
s has 3 regions, etc.
) is dictated by Euler
's formula for polyhedra
(points) + face
s (regions) - edge
s (paths) = 2.
A point in a network is either "even
" or "odd
," depending on the number of paths connected to it-- a point with 2 paths connected to it is even, a point with 1 path connected to it is odd, etc. Whether a network is "travel
able"--that is, whether it is possible to travel all paths exactly once without leaving the path--is decided solely by the number of odd points: if there are 2 or 0 odd points, the network is travelable. Otherwise, it's not.
If a point has 3 paths coming out of it--it could be any odd number, but we'll call it 3--then two possibilities
are possible: one has to arrive at the point, then leave, then arrive and be finished
; or one has to start at that point, then leave, arrive, and leave again. Thus, that odd point has to be either the start-point or the end-point. If there are exactly two odd points, fine-- one's the beginning, and one's the end. But if there are more than two, you'd have to have more than one starting point (or more than one ending point), which is clearly impossible
. And if there are no odd points, then you can start and finish wherever you want. Thus, a network must have exactly 2 or 0 odd points to be travelable. Q.E.D.
(In case you were wondering about a network with one odd point: It can't be done. Try it.)