How can you tell if a network can be traced over without lifting your pencil?

Answer 1

Each node has an even number of lines *or* there are only two nodes with odd number of lines.

Answer 2

Consider that if a point on the graph has an odd number of lines connected to it, you have to either start or finish at that point. For example, if it has 3 lines and you start there, then you go out then in then out again and you don't get stuck on that point. If you don't start there, you go in then out then in again, so if you haven't already covered the rest of the network, you're stuck.

So, if a graph has exactly two nodes with an odd number of edges, then it can be traced.

If it has no nodes with an odd number of edges (i.e. all are even), it can also be traced.

These are the only possibilities. In other words, the number of nodes with an odd number of edges has to be either 0 or 2.

Answer 3

This is a famous problem in Graph Theory.To answer this question, we can use the definition of eulerian graph.

By the idea of eulerian graph, the number of lines joining to/from the node of the network should be even.