Graph Theory
Enter edges like A-B, B-C, C-A (weights optional, e.g. A-B:4).
Vertices are inferred from edges — list them separately only to include isolated vertices.
A-B,B-C,C-D,D-A— a 4-cycle: connected, bipartite, has an Euler circuit.A-B,A-C,A-D,B-C,B-D,C-D— the complete graph K4: has a Hamiltonian cycle.A-B,A-C,A-D,A-E— a star: 4 odd-degree vertices, no Euler path.
Understanding Graph Theory
A graph is a collection of vertices (nodes) connected by edges, used to model any system of pairwise relationships: social networks, road maps, computer networks, and dependency chains all reduce to graphs. This module lets you build a graph and immediately see its structural properties — degree, connectivity, cycles — which are the building blocks for the algorithms covered in the Graph Algorithms module.
Key Definitions & Formulas
- Vertex degree: the number of edges touching a vertex.
- Path: a sequence of edges connecting a sequence of distinct vertices.
- Cycle: a path that starts and ends at the same vertex with no repeated edges.
- Connected graph: every pair of vertices has a path between them.
- Directed vs. undirected: edges can be one-way (directed) or two-way (undirected).
- Bipartite graph: vertices split into two groups with edges only between groups, never within.
Worked Example
A graph with vertices {1,2,3} and edges {(1,2),(2,3)} has 3 vertices and 2 edges — exactly one less edge than vertices, and it's connected with no cycles, which means (as this calculator's tree-checker confirms) it satisfies both conditions required to be a tree.
Where This Is Used
- Social network analysis (friend/follower graphs).
- GPS routing and network topology design.
- Dependency resolution in build systems and package managers.
- Circuit design, where components and wires form a graph.