Problem (Euler, 1736). Königsberg had four land areas joined by seven bridges. Is there a walk crossing every bridge exactly once? No: all four land areas have an odd number of bridges.
Theorem. A connected multigraph has an Euler circuit iff every degree is even, and an Euler path iff exactly 0 or 2 vertices have odd degree (the path then starts and ends at the odd ones).
int eulerKind(int n, const vector<pair<int, int>>& edges) { // 2 = circuit, 1 = path, 0 = none (undirected multigraph)
vector<int> deg(n, 0), p(n); iota(all(p), 0);
function<int(int)> f = [&](int x) { return p[x] == x ? x : p[x] = f(p[x]); };
for (auto [u, v] : edges) { deg[u]++; deg[v]++; p[f(u)] = f(v); }
int root = -1, odd = 0;
for (int v = 0; v < n; v++) if (deg[v]) { if (root < 0) root = f(v); else if (f(v) != root) return 0; odd += deg[v] % 2; }
return odd == 0 ? 2 : odd == 2 ? 1 : 0;
}Proof: Euler's theorem
Necessity. Each time a walk passes through a vertex it uses two of its edges, so only the start and end can have odd degree, and for a circuit none. The edges must also be in one connected component. Sufficiency (circuit). Start anywhere and walk along unused edges; with all degrees even, the walk can only get stuck at its start, giving a closed trail. If edges remain, some vertex on the trail has unused edges (connectivity); remaining degrees are still even, so a closed trail from there can be spliced in. Repeat until all edges are used (Hierholzer, Euler Tours). Path. With two odd vertices, add an edge between them, take a circuit, and remove the edge. Checked against brute force over all edge orders and orientations on small random multigraphs.