Graph Theory
Graph theory is the branch of mathematics that studies graphs — mathematical structures consisting of vertices (nodes) connected by edges (links) used to model pairwise relationships between objects. It was founded by Leonhard Euler in 1736 when he solved the Königsberg bridge problem. Graph theory underpins computer networks, social network analysis, circuit design, scheduling algorithms, and shortest-path computations.
Types of Graphs in Graph Theory
| Graph Type | Description | Edges | Example Application |
|---|---|---|---|
| Undirected Graph | Edges have no direction | Bidirectional | Facebook friendship network |
| Directed Graph (Digraph) | Edges have direction (arrows) | One-way | Twitter following, web links |
| Weighted Graph | Edges carry numerical weights | Weighted | Road maps with distances |
| Complete Graph Kₙ | Every vertex connects to every other | n(n-1)/2 edges | Round-robin tournament |
| Bipartite Graph | Vertices split into two disjoint sets | Only cross-set edges | Job-applicant matching |
| Tree | Connected acyclic graph | n-1 edges for n vertices | File systems, parse trees |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Vertex (graph theory)
In graph theory, a vertex (plural: vertices) is a fundamental unit representing a node, point, or entity in a graph, connected to other vertices via edges. The degree of a vertex is the number of edges incident to it, and a vertex with degree zero is called an isolated vertex. Vertices model real-world objects such as cities in a road network, computers in a network, or people in a social graph.
Edge (graph theory)
In graph theory, an edge is a connection between two vertices (nodes) representing a relationship or link between them. Edges may be directed (pointing from one vertex to another, called arcs) or undirected (bidirectional), and weighted (carrying a numerical value such as distance or cost) or unweighted. The set of all edges in a graph, together with the set of vertices, fully defines the graph's structure.
Tree (graph theory)
A tree in graph theory is a connected, undirected graph containing no cycles, which means any two vertices are joined by exactly one unique path. A tree with n vertices always has exactly n − 1 edges. Trees are foundational data structures in computer science (binary search trees, heaps, syntax trees) and appear in network design, organisational hierarchies, and phylogenetics.
The word "graph" in mathematics derives from Greek graphē, meaning "writing" or "drawing." The field was born from Euler's 1736 paper "Solutio problematis ad geometriam situs pertinentis" (Solution of a problem relating to the geometry of position), which solved the Königsberg bridge problem and introduced the first graph-theoretic argument.