1
$\begingroup$

A smart 10 year old asked me basically this question.

Consider a rectangle with both diagonals drawn in. Now ask if you can visit all the edges by travelling from some starting vertex and only ever going to a neighboring vertex but never visiting the same edge twice.

The answer is no, but is there an explanation would you could give to a smart 10 year old for this?

$\endgroup$
3
$\begingroup$

Suppose that your drawing DOES have a path that does what you say.

Any vertex is either a start or end vertex or an interior (visited along the way) vertex. If it's an interior vertex, it has an EVEN number of edges meeting it, because for each visit, there's the edge you arrived on and the edge you left on.

For a start/end vertex, it has an ODD number of edges meeting it. [But see below].

Conclusion: for a drawing with a suitable path, there are exactly two vertices with an odd number of edges meeting them. But in your example, there are 4 such vertices. Hence, no suitable path.

Revised and improved answer:

Look at each vertex of the drawing, and suppose that you had a path that traverses each edge exactly once. Begin by drawing a circle around the start and end points of the path (the two circles may be at the same vertex). At every non-circled vertex, the path arrives and leaves the same number of times, so all non-circled vertices have even degree. Conclusion: In the whole drawing, there are at most two vertices of odd degree. Your square with diagonals has 4. So the supposition that there is a "nice" path in this drawing must be incorrect.

$\endgroup$
7
  • 1
    $\begingroup$ Exactly two odd vertices would give a path through all edges of a graph. Zero odd vertices would also work, and the circuit would start and end at the same point. $\endgroup$ – suneater Apr 16 '15 at 15:49
  • $\begingroup$ I don't understand this proof. Just consider a square with no diagonals added. Your reasoning would suggest than any path has two vertices with an odd number of edges meeting it and so there is no solution as there are no such vertices ... wouldn't it? $\endgroup$ – felix Apr 16 '15 at 17:00
  • $\begingroup$ Good point -- there's one more case (as zahbaz has noted) which is that the start and end verts are the same, in which case they each contribute one extra edge at that vert, for a total of two. Summary: either 0 (if start - end) or 2 (otherwise) odd-degree verts. Certainly not 4. $\endgroup$ – John Hughes Apr 17 '15 at 3:45
  • $\begingroup$ I still think the proof needs expanding/changing although I like the underlying idea. A path can touch itself at any point. The rectangle has 6 edges so our solution path must have 7 vertices, 2 at the ends and 5 internal ones. When written out in a straight line, the ones at the end have an odd number of vertices meeting them and the internal ones have an even number. Now when we map the path to our rectangle the path can self intersect. So we have 7 integers, 5 of which are even and 2 of which are odd and we have to somehow make 4 odd numbers by summing subsets of them. Contradiction. $\endgroup$ – felix Apr 17 '15 at 11:44
  • $\begingroup$ There's a slightly cleaner way to make the same argument: look not at the whole path, but at each vertex of the drawing. First, circle the start and end points of the path (the two circles may be at the same vertex, of course, which I failed to note earlier). At every non-circled vertex, the path arrive and leaves the same number of times, so they all have even degree. Conclusion: at most two vertices of odd degree. Your square with diagonals has 4. Contradiction. $\endgroup$ – John Hughes Apr 17 '15 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.