Graph Theory Calculator: Degrees, Euler, Hamilton, Colouring, Spanning Trees and Planarity

How this calculator works

Choose a standard graph (complete, cycle, path, star, bipartite, wheel, hypercube, grid or the Petersen graph) and its size, or choose "My own graph" and type up to twelve edges as pairs of vertex numbers. Number the vertices from 1.

The calculator gives the degree of every vertex and checks the handshake lemma (the degrees add to twice the number of edges). It then tests whether the graph is connected and bipartite, whether it has an Euler circuit or trail (a walk using every edge once) and a Hamilton cycle (a closed walk through every vertex once), and finds the chromatic number, the diameter and the number of spanning trees.

The number of spanning trees comes from the matrix tree theorem. Planarity is exact for the standard graphs. For your own graph it is decided when a quick edge-count test settles it, and otherwise it tells you it is not decided. Graphs are limited to 16 vertices.

Formulas used

• \sum_{v}\deg(v) = 2E
• V - E + F = 2
• \tau(G) = \det\left(L\ \text{with one row and column removed}\right)
• \tau(K_n) = n^{n-2}

Worked example

With the default numbers in the calculator above:

1. Number of vertices: 5 vertices (Your graph)
2. Number of edges: 6 edges
3. Degrees of the vertices: 3, 2, 3, 2, 2 (vertex 1 first)
4. Handshake check: the degrees add to twice the edges: 12 = 2 x 6, so the count is consistent
5. Density: the share of all possible edges that are present: 60.00 % of the possible edges
6. Connected pieces: 1 piece: the graph is connected
7. Bipartite (can the vertices be split into two groups with every edge between the groups?): No: it contains an odd cycle
8. Euler circuit or trail (a walk using every edge exactly once): Euler trail: yes, but not a circuit. Exactly two vertices have odd degree, so a walk uses every edge once if it starts at one and ends at the other
9. Hamilton cycle (a closed walk visiting every vertex exactly once): Yes, there is a Hamilton cycle
10. Chromatic number (fewest colours so that joined vertices differ): 3 colours
11. Diameter (the longest shortest path): 2 edges
12. Number of spanning trees: 11 spanning trees

Change the numbers in the calculator to see the full working, every step, for your own case.

A second worked example

A different case, with these numbers: Which graph? Complete graph K(n): every vertex joined to every other; Number of vertices (n). For the hypercube the dimension, for a grid the rows, for K(n,m) the size of the first group 5.

1. Number of vertices: 5 vertices (Complete graph K5)
2. Number of edges: 10 edges
3. Degrees of the vertices: 4, 4, 4, 4, 4 (vertex 1 first)
4. Handshake check: the degrees add to twice the edges: 20 = 2 x 10, so the count is consistent
5. Density: the share of all possible edges that are present: 100.00 % of the possible edges
6. Connected pieces: 1 piece: the graph is connected
7. Bipartite (can the vertices be split into two groups with every edge between the groups?): No: it contains an odd cycle
8. Euler circuit or trail (a walk using every edge exactly once): Euler circuit: yes. Every degree is even, so a closed walk uses every edge exactly once
9. Hamilton cycle (a closed walk visiting every vertex exactly once): Yes, there is a Hamilton cycle
10. Chromatic number (fewest colours so that joined vertices differ): 5 colours
11. Diameter (the longest shortest path): 1 edge
12. Number of spanning trees: 125 spanning trees

Common questions

Related calculators

• Permutations and Combinations Calculator: nPr, nCr and Binomial Probability
• Venn Diagram Calculator: Inclusion-Exclusion for Two or Three Sets
• GCD and LCM Calculator With Prime Factors and Modular Inverse

Got a question about this? Ask an engineering question and get a plain-language answer with references.

Further reading: Any discrete mathematics text (Rosen, Discrete Mathematics and Its Applications, chapters on graphs and trees); West, Introduction to Graph Theory.

← All engineering calculators