Graph Properties Calculator
Calculate graph density, average degree, edge count, and analyze degree sequences.
Check Euler path conditions and tree/complete graph status.
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
| Property | Undirected Formula | Directed Formula |
|---|---|---|
| Max edges | n(n−1)/2 | n(n−1) |
| Density | m / [n(n−1)/2] | m / [n(n−1)] |
| Avg degree | 2m / n | m / n |
Where n = vertices, m = edges.
Density ranges from 0 (no edges) to 1 (every possible edge exists). A density above 0.5 is generally considered a dense graph.
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). This means the degree sum must always be even — if it’s odd, the sequence is impossible.
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.31 (sparse)
- Average degree = 2×14/10 = 2.8 roads per intersection