Graph Properties Calculator

Graph Theory Fundamentals

A graph G = (V, E) consists of a set of vertices (nodes) V and edges (connections) E. Graphs model networks of all kinds: roads, social connections, computer networks, and more.

Key Properties

Where n = vertices, m = edges.

Density ranges from 0 (no edges) to 1 (every possible edge exists). There is no official cut-off between sparse and dense, and different fields draw it in different places. This calculator calls anything under 0.3 sparse, 0.3 to 0.7 moderate, and above 0.7 dense, and says which band a graph falls into. Treat those as labels for reading the number, not as definitions.

Trees

A tree is a connected, acyclic graph. It always has exactly n−1 edges. If your graph has n−1 edges, it may be a tree (if also connected).

Complete Graphs

A complete graph Kₙ has every vertex connected to every other vertex. Kₙ has exactly n(n−1)/2 edges (undirected).

Degree Sequences and the Handshaking Lemma

The sum of all vertex degrees always equals 2m (twice the number of edges). So the degree sum must be even. An odd sum means no graph can have that sequence.

An even sum is necessary but not sufficient. Take [3, 3, 1, 1]: the sum is 8, which passes the handshaking test, yet no graph has those degrees. Two vertices of degree 3 among four vertices must each connect to all three others, which forces the remaining two vertices to have degree 2 or more, not 1. The proper test is the Havel-Hakimi algorithm: repeatedly remove the largest degree d and subtract 1 from the next d entries. If you ever run out of entries or go negative, the sequence is not graphical. This calculator runs that test rather than stopping at the even-sum check.

Euler Paths and Circuits

• Euler Circuit (visits every edge exactly once, returns to start): exists if and only if every vertex has even degree.
• Euler Path (visits every edge exactly once, doesn’t need to return): exists if exactly 0 or 2 vertices have odd degree.

Real-World Example

A city road network with 10 intersections (vertices) and 14 roads (edges) has:

• Density = 14 / (10×9/2) = 14/45 ≈ 0.311, which lands just inside the moderate band
• Average degree = 2×14/10 = 2.8 roads per intersection

That 0.311 is worth pausing on. It sits a whisker above the 0.3 line, which is a good reminder that the sparse/moderate/dense labels are conveniences rather than facts about the graph. A real road network is sparse in the way that matters: intersections join three or four roads no matter how large the city gets, so density falls towards zero as n grows even though the average degree stays put. That is the usual meaning of a sparse graph, m growing like n rather than like n².