Graph Theory Calculator

Visualize and analyze graphs with our interactive graph theory tool. Calculate shortest paths, minimum spanning trees, and more.

Undirected Graph
Directed Graph
Weighted Graph
Tree
Add Node
Add Edge
Move Node
Delete
Nodes
0
Edges
0
Graph Type
Undirected
Connected
No

Graph Algorithms

Apply algorithms to analyze your graph

Algorithm Result
Select an algorithm to see results

Graph Representation

View different representations of your graph

Node
Select nodes to see adjacency list
Select edges to see edge list

Graph Theory Concepts

Graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

Key Concepts: Graphs consist of vertices (nodes) connected by edges. Graphs can be directed or undirected, weighted or unweighted.

Graph Types

  • Undirected Graph: Edges have no direction (A-B is same as B-A)
  • Directed Graph (Digraph): Edges have direction (A→B is different from B→A)
  • Weighted Graph: Edges have weights (costs or distances)
  • Tree: A connected acyclic graph with no cycles
  • Connected Graph: There is a path between every pair of vertices
  • Complete Graph: Every pair of distinct vertices is connected by an edge
Graph Theory Examples

Complete Graph (Kn):

Every pair of distinct vertices is connected by a unique edge

K3: Triangle with 3 vertices and 3 edges

K4: Tetrahedron with 4 vertices and 6 edges

Cycle Graph (Cn):

Vertices connected in a closed chain

C3: Triangle

C4: Square

C5: Pentagon

Tree:

Connected acyclic graph

Properties: n vertices, n-1 edges

Examples: Binary tree, star graph

Bipartite Graph:

Vertices divided into two disjoint sets

All edges connect vertices from different sets

Examples: Complete bipartite K3,3

Graph Algorithms
Breadth-First Search (BFS)

Visits all vertices level by level

Applications: Shortest path in unweighted graphs

Time complexity: O(V + E)

Depth-First Search (DFS)

Explores as far as possible along each branch

Applications: Cycle detection, topological sorting

Time complexity: O(V + E)

Dijkstra's Algorithm

Finds shortest paths from a source vertex

Works for weighted graphs with non-negative weights

Time complexity: O(V²) or O(E + V log V) with heap

Prim's Algorithm

Finds minimum spanning tree for weighted graphs

Greedy algorithm that grows the tree one vertex at a time

Time complexity: O(V²) or O(E log V) with heap

Frequently Asked Questions

A graph is a collection of vertices (nodes) connected by edges (links). It can have cycles and be disconnected.

A tree is a special type of graph that:

  • Is connected (all vertices are reachable from any other vertex)
  • Has no cycles
  • Has exactly n-1 edges for n vertices

All trees are graphs, but not all graphs are trees.

There are two common ways to represent graphs:

  1. Adjacency Matrix:
    • A 2D array of size V×V (V = number of vertices)
    • matrix[i][j] = 1 if there is an edge from vertex i to vertex j
    • Pros: Simple implementation, easy to check edge existence
    • Cons: Memory intensive (O(V²)), inefficient for sparse graphs
  2. Adjacency List:
    • An array of lists, where each list stores neighbors of a vertex
    • Pros: Memory efficient (O(V+E)), good for sparse graphs
    • Cons: Harder to check if an edge exists

This calculator supports both representations.

Breadth-First Search (BFS) and Depth-First Search (DFS) are two fundamental graph traversal algorithms:

Feature BFS DFS
Approach Level by level Branch by branch
Data Structure Queue Stack
Memory Usage More memory (stores all nodes at current level) Less memory (only stores path from root)
Applications Shortest path in unweighted graphs, peer-to-peer networks Topological sorting, cycle detection, path finding
Time Complexity O(V+E) O(V+E)

Dijkstra's algorithm is used to find the shortest path between nodes in a graph with non-negative edge weights.

Key characteristics:

  • Works for both directed and undirected graphs
  • Uses a priority queue to select the next node to visit
  • Time complexity: O(E log V) with a min-heap
  • Doesn't work for graphs with negative weight edges

Applications:

  • Network routing protocols
  • Geographic navigation systems
  • Traffic management systems
  • Robotics path planning

A bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that:

  • Every edge connects a vertex in U to one in V
  • No edge connects vertices within the same set

Properties:

  • All trees are bipartite
  • All even-length cycles are bipartite
  • No odd-length cycles
  • Chromatic number is 2

Applications:

  • Matching problems (job assignments, dating apps)
  • Collaboration networks
  • Recommender systems

Detecting cycles in a graph can be done using several methods:

  1. Depth-First Search (DFS):
    • Track visited nodes and recursion stack
    • If you encounter a node that's in the recursion stack, a cycle exists
    • Time complexity: O(V+E)
  2. Union-Find (Disjoint Set):
    • For undirected graphs
    • If adding an edge connects two already connected components, a cycle exists
    • Time complexity: O(E α(V)) where α is inverse Ackermann function
  3. Topological Sorting:
    • For directed graphs (DAGs)
    • If topological sort fails (cannot find vertex with zero in-degree), cycle exists
    • Time complexity: O(V+E)

This calculator automatically detects cycles when analyzing graphs.

The Four Color Theorem states that:

Any planar graph can be colored with at most four colors such that no two adjacent vertices share the same color.

Key points:

  • Proved in 1976 by Kenneth Appel and Wolfgang Haken
  • First major theorem proved using computer assistance
  • Applies to maps and planar graphs
  • Doesn't apply to non-planar graphs
  • Practical applications in map making, scheduling, and register allocation

This calculator computes the chromatic number of graphs, which for planar graphs will be ≤4.

Graph theory has numerous real-world applications:

  • Social Networks: Friend networks, influencer detection
  • Transportation: Route planning, traffic optimization
  • Computer Networks: Routing algorithms, network design
  • Biology: Protein interaction networks, phylogenetic trees
  • Recommendation Systems: Product recommendations, content discovery
  • Web Search: PageRank algorithm for ranking web pages
  • Circuit Design: PCB layout, logic gate optimization
  • Operations Research: Resource allocation, scheduling
  • Chemistry: Molecular structure representation
  • Artificial Intelligence: Knowledge representation, neural networks