Mathematics Atlas

How Proof Is Made
Sign In
Text size
100%
Theme

Switch Atlas

Branches of Mathematic

Graph Theory

Combinatorics and Graph Theory

Graph theory is the study of graphs, mathematical structures of vertices connected by edges, used to model pairwise relations between objects. It originated with Leonhard Euler's 1736 solution to the Seven Bridges of Konigsberg problem, and has grown from a branch of combinatorics into a stand-alone field with applications throughout computer science and network science. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/

Facts
Central Question
Which structural properties of a network of vertices and edges, connectivity, colorability, the existence of an optimal path or cycle, can be established from its combinatorial structure alone, independent of what the vertices and edges are taken to represent? 1
Key Debate
Whether graph theory is best understood as a subfield of combinatorics or as a stand-alone branch in its own right; its rapid post-1950s growth, driven by applications in computer science, operations research and network science, gave it a body of problems distinct enough that most mathematicians now treat it as independent. 1
Classification
Pure or Applied
Both / Interdisciplinary 1
Connections

Associated With

Four Color Theorem, Theorems

The theorem is already In Branch topology (its long proof history is topological) but its statement, that any planar map can be colored with four colors so that no two bordering regions match, is the textbook graph-coloring result once the map is translated to its dual graph; graph-theory's own key-debate names exactly this kind of colorability question as central to the branch. A second branch tie, not a replacement for the topology one.

Leonhard Euler, Mathematicians

Founding problem: the Seven Bridges of Konigsberg, 1736.

Source Graph Theory (Wikipedia)

Includes

Brooks' Theorem, Theorems
Cayley's Formula, Theorems
Erdos-Gallai Theorem, Theorems
Graph (Discrete Mathematics), Concepts
Source Graph (Discrete Mathematics) (Wikipedia)
Hall's Marriage Theorem, Theorems
Hypergraph, Concepts
Kirchhoff's Theorem (Matrix-Tree Theorem), Theorems
Koenig's Theorem (Graph Theory), Theorems
Kruskal's Tree Theorem, Theorems
Kuratowski's Theorem, Theorems
Menger's Theorem, Theorems
Ore's Theorem, Theorems
Petersen Graph, Mathematical Objects
Source Petersen Graph (Wikipedia)
Robbins' Theorem, Theorems
Robertson-Seymour Theorem, Theorems
Turan's Theorem, Theorems
Tutte-Berge Formula, Theorems
Tutte's Theorem (Graph Theory), Theorems
Vizing's Theorem, Theorems
Sources
1. Graph Theory (Wikipedia)
Wikipedia
  • Lead and history sections
    the study of graphs, which are mathematical structures used to model pairwise relations between objects
  • Overview of research areas
    Is it true that any map drawn in the plane may have its regions colored with four colors
  • Overview, on the field's standing
    a stand-alone field due to its great growth and distinct from other fields, having its own kind of problems
  • Lead section, pure or applied classification
    In mathematics and computer science, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
  • Associated With: Leonhard Euler, History section
    is regarded as the first paper in the history of graph theory
View the Source
Petersen Graph (Wikipedia)
Wikimedia FoundationIncludes: Petersen GraphView the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.