This lesson presents interesting and challenging problems in Graph Theory, supporting the skills that students learned at school and stimulating their critical thinking. The topics will include: basic properties of graphs; complete graphs and complete bipartite graphs; planar and plane graphs; and Euler’s formula - the four-color theorem. These topics have many applications in electrical circuits, computer programs, and the scheduling of aircraft and trains. Here we shall discuss two applications - the three-utilities/three-houses problem and the avoiding crossing on the motherboard. No prerequisites are required for this lesson, and it can be considered self-contained. It will last about 26 minutes, and the remaining time will be devoted to different in-class activities, such as connecting the three houses to the three stations, coloring a plane map with a minimum number of colors, discovering Euler’s formula (which relates the number of vertices, number of edges and the number of faces in a plane graph), and representing the motherboard of a calculator without crossing. Supplies needed for these activities include papers, colors, wires, threads, ropes with different colors, cardboard, balloons, and a car tube. Find Teacher’s Guide and downloadable graphs in section “For Teachers”.