Graph Theory
Graph theory studies graphs - structures of vertices joined by edges - as mathematical models of pairwise relations and networks.
Definition
The mathematical study of graphs, which are sets of vertices together with a set of edges each joining a pair of vertices, and of the properties invariant under the structure of those connections.
Scope
The area covers the structure, properties, and parameters of graphs: connectivity, paths and cycles, trees, planarity, colorings, matchings, and flows, as well as extremal and probabilistic questions about how graph properties constrain one another. It is central to discrete mathematics and supplies the language for networks across computer science, operations research, and the natural and social sciences.
Sub-topics
Core questions
- What structural properties follow from a graph's connectivity, degree sequence, or cycle structure?
- When can a graph be drawn in the plane without crossings or colored with few colors?
- How large or dense can a graph be while avoiding a given substructure?
- How do paths, matchings, and flows let one optimize over a network?
Key concepts
- Vertices, edges, and degree
- Connectivity and components
- Paths, cycles, and trees
- Planarity
- Graph coloring
- Matchings and flows
Clinical relevance
Graphs model communication and transport networks, social and biological interaction networks, circuit and dependency structures, and scheduling problems, making graph theory a foundational tool in computer science and operations research.
History
Graph theory traces to Euler's 1736 solution of the Konigsberg bridges problem and matured in the 20th century through work on coloring, connectivity, and the probabilistic and structural methods of Erdos, Tutte, and others.
Key figures
- Leonhard Euler
- William Tutte
- Bela Bollobas
Related topics
Seminal works
- diestel2017
- bollobas1998
Frequently asked questions
- What is the difference between a graph and a network?
- A graph is the abstract mathematical object of vertices and edges; a network usually refers to a graph endowed with extra data such as weights, capacities, or directions modeling a real system.
- Why was the Konigsberg bridge problem important?
- Euler's proof that no walk could cross each of the seven bridges exactly once abstracted the problem to vertices and edges, founding graph theory and topology.