The goal is to trace a line with your pencil across each edge on the box only once without crossing the vertices or picking your pencil up.

Note that this "box" contains 16 unique "edges".

Prove why this is an impossible task regardless of where you first place your pencil.

For sake of argument we'll call any system of nodes and segments a network as long as the following conditions are met:

There is at least 1 node,
There are at least N-1 segments, where N is the numebr of nodes,
There is a path which connects each node with every other node in the network (no group of nodes is separate from another group of nodes.)
All segments must be connected to a node at each end.

Any node which is connected to an even number of nodes is called an even node, and any node which is connected to an odd number of nodes is called an odd node.  A node's value will be defined by the number of segments connected to it.  Any segment which is connected to the same node at both ends will be counted as 2.

Any network which contains only even valued nodes will be called an even network and any network which contains odd valued nodes will be called an odd network.

It can be shown that the total value of any network must be even because any time you introduce a new segment you add 1 for each segment end that is connected.  Therefore, there must always be zero or an even number of even nodes and zero or an even number of odd nodes.

For a network to be traversable you must be able to traverse each segment of the network.  For this to be possible the ends of the segments can be labeled "Out" when you exit a node and "In" when you enter a node.  For a network which consists only of even nodes it can be shown that the network is traversable by assigning an equal number of "In" and "Out" segment ends to each node (each segment will still have 1 "In" and 1 "Out".  Any node can be assigned as a starting node, and it can be seen that every other node has 1 exiting segment for each entering segment.

Any even network can be turned into an odd network by connecting a segment between any two different nodes.  Both nodes' values will be increased by one thereby converting two even nodes to odd nodes.  Any odd network can be converted to an even network by systematically connecting pairs of odd nodes until no further odd nodes exist.

It was shown earlier that any even network is traversable by assigned equal numbers of Ins and Outs to each node.  In an odd network, the odd nodes must have at least 1 more In than Out or 1 more Out than in.  For a network consisting of only 1 pair of odd nodes, you assign the node with 1 more Out as the starting node and the node with 1 more In as the ending node.  All the even nodes in the network will have an equal number of Ins and Outs.  It can be shown that this network is traversable because each node which is entered has a way of exiting.

For any network with 2 or more pairs of odd nodes it will be seen that there must exist 2 or more starting nodes and an equal number of ending nodes.  Once a network has more than one starting node, the network is no longer traversable.

In the given puzzle, there are 2 pairs of odd nodes (the outside of the box is also odd because there are 9 segment ends connected to it), therefore it is not traversable.


Hopefully my mad, hurried ramblings make sense.  I left out a fair amount of detail for this to be a real proof, like the bit that just because a network is traversable doesn't mean that every sequence of paths results in a full solution, nor do I describe how to eliminate this condition.