In
geometry, a network is a number of
points, with
line segments connecting them. The number of points, line segments (called "paths"), and
regions (how many "spaces" within the network, including the
exterior-- a
square has 2 regions, a square divided into two
triangles has 3 regions,
etc.) is dictated by
Euler's formula for
polyhedra--
vertices (points) +
faces (regions) -
edges (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 "
travelable"--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.
Reasoning:
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.)