We formalize the notions of walks, paths, and cycles, then develop the theory of connected components, vertex and edge connectivity, cut vertices and bridges, the characterization of bipartite graphs, and Menger's theorem.
Beginning with the definition of cosets of a subgroup, we prove Lagrange's theorem --- the assertion that the order of a subgroup divides the order of the group. As applications, we derive Fermat's little theorem and Euler's theorem, and we exhibit the alternating group A_4 as a counterexample to the converse.
Strongly connected components (SCCs), Tarjan's and Kosaraju's algorithms, DAGs and topological sorting, the correspondence with partial orders, and dynamic programming on DAGs.
From the definition of a graph to planarity, coloring, and matroids. A textbook series building definitions, theorems, and proofs in a systematic progression.
From the axioms to the classification of finite groups. A textbook series building definitions, theorems, and proofs in a systematic progression.
From divisibility and congruences to p-adic numbers and algebraic integers. A textbook series building definitions, theorems, and proofs in a systematic progression.
From the axioms of vector spaces to Jordan normal form. A textbook series building definitions, theorems, and proofs in a systematic progression.
The quotient group G/N is the first major conceptual hurdle in group theory. By computing small examples by hand -- from clock arithmetic to D4 modulo its center -- we build the intuition for what "dividing" a group really means, and why normality is indispensable.
We formalize the notions of walks, paths, and cycles, then develop the theory of connected components, vertex and edge connectivity, cut vertices and bridges, the characterization of bipartite graphs, and Menger's theorem.
Beginning with the definition of cosets of a subgroup, we prove Lagrange's theorem --- the assertion that the order of a subgroup divides the order of the group. As applications, we derive Fermat's little theorem and Euler's theorem, and we exhibit the alternating group A_4 as a counterexample to the converse.
Strongly connected components (SCCs), Tarjan's and Kosaraju's algorithms, DAGs and topological sorting, the correspondence with partial orders, and dynamic programming on DAGs.
We prove the equivalent characterizations of trees, establish the formula $|E|=|V|-1$, introduce rooted trees and Cayley's formula, and develop the theory of spanning trees and minimum spanning trees via Kruskal's and Prim's algorithms.
Create an account to get article and series recommendations tailored to your interests.
Create Free Account