Graphs, degree, and paths

Each edge is counted exactly twice when we sum degrees: once from each of its two endpoints. So the sum is even, and since the even-degree vertices already contribute an even amount to the total, the odd-degree vertices must appear an even number of times.

Take any finite graph $G = (V, E)$. Build the set of all vertex-edge incidence pairs $(v, e)$ where vertex $v$ is an endpoint of edge $e$, and count this set two different ways. Counting by vertex: each vertex $v$ contributes exactly $\deg(v)$ incidence pairs (one for every edge touching it), so the total count is $\sum_{v \in V} \deg(v)$. Counting by edge: every edge $e = \{u, w\}$ has exactly $2$ endpoints, $u$ and $w$, so it contributes exactly $2$ incidence pairs, and summing over all $|E|$ edges gives $2|E|$.

Since both counts tally the same set of pairs, they must agree: $\sum_{v \in V} \deg(v) = 2|E|$. For the second claim, split the sum into vertices of even and odd degree: $\sum_{v \text{ even}} \deg(v)$ is a sum of even numbers, hence even, so $\sum_{v \text{ odd}} \deg(v)$ must also be even (their total $2|E|$ is even). A sum of odd numbers is even only when there is an even number of terms, so the number of odd-degree vertices $O$ is even.

Follow any trail; each time you pass through a vertex (other than the start/end) you use up two of its edges, so a vertex where you could get stuck (other than the two endpoints) must have even degree — this is the easy direction. The converse (even degree is enough) follows by an inductive argument: peel off closed trails and splice them together (Hierholzer's construction, 1873).

(Necessity.) Suppose a connected graph $G$ has an Eulerian circuit $C$, a closed trail using every edge exactly once. Every time $C$ passes through a vertex $v$ other than the start/end vertex, it enters along one edge and leaves along a different, previously unused edge, consuming exactly $2$ of $v$'s incident edges; since $C$ uses every edge of $v$ exactly once by the time it finishes, $\deg(v)$ must be even for every vertex, including the start/end vertex where the first departing edge pairs with the final arriving edge.

(Sufficiency.) Suppose instead every vertex of the connected graph $G$ has even degree. Start at any vertex and greedily walk along unused edges; because every vertex has even degree, whenever the walk enters a vertex other than the start it can always leave again (an even number of incident edges can never be reduced to exactly $1$ unused edge), so the walk cannot get stuck except back at the starting vertex, producing a closed trail $C$. If $C$ already uses every edge, we are done. Otherwise, since $G$ is connected, some vertex $v$ on $C$ has an unused incident edge; the unused edges also all have even degree at every vertex (removing the even-degree closed trail $C$ preserves parity), so by the same argument they form another closed trail $C'$ through $v$. Splicing $C'$ into $C$ at $v$ produces a longer closed trail; repeating this splicing process (Hierholzer's construction, 1873) until no unused edges remain yields an Eulerian circuit.

If some $S$ has $|N(S)| < |S|$, the vertices of $S$ have nowhere near enough neighbours to be matched injectively, so the condition is clearly necessary. That it is also sufficient is proved by finding an augmenting path whenever a matching is not yet complete (the König–Egerváry augmenting-path argument).

(Necessity.) If some $S \subseteq X$ had $|N(S)| < |S|$, then the vertices of $S$ have fewer than $|S|$ possible partners among all of $Y$ combined, so no matching can inject $S$ into $Y$ injectively — hence no matching covering all of $X$ can exist. So Hall's condition $|N(S)| \ge |S|$ is clearly necessary.

(Sufficiency.) Suppose Hall's condition holds but some matching $M$ leaves a vertex $x_0 \in X$ unmatched. Build an alternating tree from $x_0$: follow non-matching edges out of $X$-vertices and matching edges back from $Y$-vertices, exploring all vertices reachable this way. If this tree ever reaches a $Y$-vertex $y$ not covered by $M$, the path from $x_0$ to $y$ alternates non-matching/matching edges and has odd length, so swapping matched and unmatched edges along it (taking the symmetric difference $M \triangle P$) strictly increases the matching size by one, contradicting that $M$ was already as large as possible along this branch — repeat until no unmatched $x_0$ remains, or Hall's condition is violated on the set $S$ of $X$-vertices reached, since then every $Y$-vertex reached is matched back into $S$, forcing $|N(S)| \le |S| - 1$. Since Hall's condition holds by assumption, this contradiction cannot occur, so every vertex of $X$ must eventually be matched — this is the König–Egerváry augmenting-path argument.

$K_5$ and $K_{3,3}$ are themselves non-planar (checked directly with Euler's formula $V - E + F = 2$), and any subdivision (replacing edges by paths) preserves non-planarity. Kuratowski's 1930 theorem is the surprising converse: these two graphs are the only obstructions.

(Necessity: $K_5$, $K_{3,3}$, and their subdivisions are non-planar.) In any connected simple planar graph with $V \ge 3$ drawn without crossings, every face $F$ is bounded by at least $3$ edges and each edge borders at most $2$ faces, so counting edge-face incidences gives $2E \ge 3F$. Substituting $F = E - V + 2$ from Euler's formula $V - E + F = 2$ yields $2E \ge 3(E - V + 2)$, i.e. $E \le 3V - 6$. For $K_5$ we have $V = 5$ and $E = 10$, violating $3V - 6 = 9 < 10$, so $K_5$ is non-planar. For the bipartite graph $K_{3,3}$, there are no odd cycles (hence no triangles), so every face requires at least $4$ edges: $2E \ge 4F$, which combines with $V - E + F = 2$ to give $E \le 2V - 4$. Since $K_{3,3}$ has $V = 6$ and $E = 9$, violating $2V - 4 = 8 < 9$, $K_{3,3}$ is also non-planar.

Subdividing an edge (replacing it by a path through new vertices of degree $2$) does not affect whether a graph can be drawn in the plane without crossings, so any graph containing a subdivision of $K_5$ or $K_{3,3}$ is non-planar. For the converse (sufficiency), proved by Kuratowski in 1930, one proceeds by induction on $|V| + |E|$: a minimal non-planar graph $G$ must be $3$-connected, and deleting an edge $e$ produces a planar graph $G - e$ whose cycle around the endpoints of $e$ has alternating chords on both the inside and the outside, which forces a subdivision of either $K_5$ or $K_{3,3}$ inside $G$.