Connectedness, paths, cycles and tracing a graph

Count connected components, find the vertices of odd degree and decide whether a graph can be traced without lifting the pencil.

Guide

In the Russian programme (Grade 7, Probability and Statistics, introduction to graph theory) after vertices, edges and degree come: a chain (a path: each edge begins where the last ended), a cycle (a chain returning to its start) and connectedness (any two vertices are joined by a chain). Every graph falls apart into connected components.

An Euler path uses every edge exactly once. It exists when the graph is connected and has zero or two vertices of odd degree. With zero, a closed tour (Euler cycle) exists; with two, the path starts at one and ends at the other. This settles the Konigsberg bridges (four odd vertices) and "can you draw the figure without lifting the pencil".

Common slips: not counting a lone vertex as a component; counting vertices instead of edges for the degree; thinking every figure can be drawn in one stroke.