Graph Theory Calculator
Analyse a graph from its edge list: degrees, connectivity, Euler circuits and paths, bipartiteness, the adjacency matrix and the number of spanning trees.
About the Graph Theory Calculator
The handshake lemma says the degrees add up to twice the number of edges. A connected graph has an Euler circuit (using every edge once and returning) when every degree is even, and an Euler path when exactly two degrees are odd. A graph is bipartite when its vertices split into two sets with every edge between them, which happens exactly when it has no odd cycle.
Kirchhoff's matrix-tree theorem counts spanning trees: delete one row and column of the Laplacian (degrees on the diagonal, −1 for each edge) and take the determinant.
The formula
Σ deg(v) = 2|E|; spanning trees = any cofactor of L = D − A
- Euler circuit
- connected, all degrees even
- Euler path
- connected, exactly two odd degrees
Worked example
A-B, B-C, C-D, D-A, A-C
- Degrees A 3, B 2, C 3, D 2
- Euler path from A to C; 8 spanning trees
Questions people ask
Can I use a directed graph?
Not here: edges are undirected, and repeated edges count once.
How are spanning trees counted exactly?
The determinant is computed with exact integers, so even large counts are exact.