All Tools

Graph Theory Explorer

Build and analyze graphs interactively. Add vertices and edges, run BFS and DFS traversals, find shortest paths with Dijkstra's algorithm, compute minimum spanning trees with Prim's algorithm, and detect Eulerian circuits and paths.

Graph Canvas

Default node
Selected
Edge source
Traversed
Load a preset or switch to Add Node mode

Click a node or edge to select it. Drag nodes to reposition.

Graph Options

Edit Mode

Presets

Graph Info

Nodes
0
Edges
0

Reference Guide

Graph Basics

A graph G = (V, E) consists of a set of vertices V and a set of edges E connecting pairs of vertices. Graphs model networks, relationships, and connections.

deg⁡(v)=number of edges incident to v\deg(v) = \text{number of edges incident to } v

The degree sequence is the sorted list of vertex degrees. For any graph, the sum of all degrees equals twice the number of edges (Handshaking Lemma).

∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|

The complete graph Kₙ has n vertices and every pair connected by an edge, giving (n2)=n(n−1)2\binom{n}{2} = \frac{n(n-1)}{2} edges. K₃ has 3 edges; K₅ has 10 edges.

Shortest Paths

Dijkstra's algorithm finds the shortest weighted path from a source vertex to all other vertices. It works on graphs with non-negative edge weights.

The algorithm maintains a set of unvisited vertices and a distance table. At each step it selects the unvisited vertex with minimum tentative distance, relaxes its neighbors, and marks it visited.

d[v]=min⁡(d[v],  d[u]+w(u,v))d[v] = \min(d[v],\; d[u] + w(u,v))

Time complexity is O((∣V∣+∣E∣)log⁡∣V∣)O((|V| + |E|) \log |V|) with a binary heap. BFS finds shortest paths in unweighted graphs in O(∣V∣+∣E∣)O(|V| + |E|) time.

Eulerian & Hamiltonian

An Eulerian circuit visits every edge exactly once and returns to the start. An Eulerian path visits every edge exactly once but may end at a different vertex.

Euler's Theorem (1736): A connected undirected graph has an Eulerian circuit if and only if every vertex has even degree. It has an Eulerian path if and only if exactly two vertices have odd degree.

A Hamiltonian cycle visits every vertex exactly once. Unlike Eulerian detection, determining if a Hamiltonian cycle exists is NP-complete — no efficient algorithm is known.

The Petersen graph is a famous example that is Hamiltonian but not Eulerian (all vertices have degree 3, which is odd).

Minimum Spanning Trees

A spanning tree of a connected graph G is a subgraph that includes all vertices and is a tree (connected, acyclic). It has exactly |V| - 1 edges.

Prim's algorithm builds the MST greedily: start from any vertex, repeatedly add the minimum-weight edge that connects a tree vertex to a non-tree vertex.

Kruskal's algorithm sorts all edges by weight and adds them one by one, skipping edges that would form a cycle. Both algorithms produce the same MST (when edge weights are distinct).

w(MST)≤w(T) for all spanning trees Tw(\text{MST}) \leq w(T) \text{ for all spanning trees } T

MSTs are used in network design, clustering, and approximation algorithms for the traveling salesman problem.