Solving tracing problems using graph theory

A couple of weeks ago, I was looking at a standardized test and came across the following “tracing” problem:

Which of the drawings below can you completely trace without lifting your pencil or retracing a previously traced part? 

01_pencilliftprobs_original

When I was a teenager, I had seen similar questions to this one, but was always frustrated that I couldn’t figure out a way to solve them except by trial and error. Twenty years later, thanks to being exposed to different areas of mathematics as a tutor, I instantly saw a systematic way to answer them. Try solving the test question on your own first before reading my approach below.
Continue reading “Solving tracing problems using graph theory”