Graph theory is the branch of mathematics concerned with graphs: abstract structures consisting of vertices and edges that connect them. It studies adjacency, connectivity, routes, and structural constraints independently of the physical objects being represented. Closely associated with combinatorics and computer science, it provides a common language for problems involving roads, communication networks, molecular structures, and possible moves in puzzles. A graph in this sense represents relationships, rather than necessarily being a plotted curve. (web.math.princeton.edu)
Origins and basic definitions
A foundational episode was Leonhard Euler’s solution of the Seven Bridges of Königsberg problem in 1736. The question was whether a walk could cross each of seven bridges exactly once. Representing land areas as vertices and bridges as edges exposed the decisive feature: all four vertices had odd degree, making such a walk impossible. The argument shifted attention from distances and shapes to the pattern of connections. (ocw.mit.edu)
A graph is commonly written (G=(V,E)), where (V) is its vertex set and (E) its edge set. In a simple undirected graph, each edge is an unordered pair of distinct vertices; loops and multiple edges between the same pair are excluded. A directed graph instead uses ordered pairs, distinguishing a connection from (u) to (v) from one in the reverse direction. Other conventions permit loops or parallel edges, while weighted graphs attach numerical values such as costs or lengths to edges. (ocw.mit.edu)
The degree (\deg(v)) of a vertex counts its incident edges, with a loop counted twice in an undirected graph. For every finite undirected graph, the handshaking identity states [ \sum_{v\in V}\deg(v)=2|E|. ] Consequently, the number of odd-degree vertices is even. These facts follow because every edge contributes two incidences to the total. (ocw.mit.edu)
Connectivity, paths, and trees
A walk follows successive edges and may repeat vertices or edges. A path has no repeated vertices, while a cycle returns to its starting vertex without otherwise repeating vertices. An undirected graph is connected if every pair of vertices is joined by a path. Its connected components are the maximal connected subgraphs. Connectivity therefore describes whether movement between vertices is possible, not how short or inexpensive that movement is. (ocw.mit.edu)
A tree is a connected undirected graph containing no cycles. Between any two vertices of a tree there is exactly one path, and a finite tree with (n) vertices has (n-1) edges. A forest is an acyclic graph whose components are trees. A spanning tree retains all vertices of a connected graph while selecting enough edges to remain connected without cycles. (ocw.mit.edu)
An Eulerian trail uses every edge exactly once; an Eulerian circuit additionally ends where it begins. For a finite undirected graph with at least one edge, a circuit exists precisely when all nonisolated vertices belong to one connected component and every vertex has even degree. An open Eulerian trail exists precisely when that connectivity condition holds and exactly two vertices have odd degree. (ocw.mit.edu)
Coloring and planarity
A proper vertex coloring assigns colors so that adjacent vertices receive different colors. The chromatic number is the smallest number of colors required. A nonempty graph is bipartite when its vertices can be partitioned into two sets with every edge joining different sets; equivalently, it admits a proper coloring with at most two colors. Such graphs have no odd-length cycles. Coloring models situations in which connected objects must receive incompatible assignments. (ocw.mit.edu)
A planar graph can be drawn in the plane without edges crossing except at shared endpoints. For a connected plane drawing, Euler’s formula is [ |V|-|E|+|F|=2, ] where (F) includes the unbounded outer face. A simple planar graph with at least three vertices consequently has at most (3|V|-6) edges. The four-color theorem states that every finite planar graph admits a proper vertex coloring using at most four colors. Planarity concerns the existence of a suitable drawing, not the appearance of one particular drawing. (ocw.mit.edu)
Algorithms and computational problems
Graphs can be stored using different data structures. An adjacency list records each vertex’s neighbors and requires storage proportional to (|V|+|E|). An adjacency matrix records connections by row and column, using quadratic storage in the number of vertices. These representations support different approaches to graph processing. (ocw.mit.edu)
A graph algorithm often answers a reachability or optimization question. Breadth-first search explores vertices in layers and solves the unweighted shortest-path problem, minimizing the number of edges from a starting vertex. Dijkstra’s algorithm handles weighted shortest paths when edge weights are nonnegative. (ocw.mit.edu)
Other apparently similar problems have different computational complexity. A Hamiltonian cycle visits every vertex exactly once before returning to its start, whereas an Eulerian circuit must cover edges. Deciding whether a general finite graph has a Hamiltonian cycle is NP-complete. The distinction between visiting vertices and traversing edges thus leads to substantially different computational problems. (live.ocw.mit.edu)
Algebraic methods and applications
Spectral graph theory connects graph structure with linear algebra through associated matrices and their eigenvalues and eigenvectors. For a simple undirected graph, the adjacency matrix (A) records edges, while the diagonal matrix (D) records vertex degrees. The Laplacian is (L=D-A). The multiplicity of its zero eigenvalue equals the number of connected components, providing an algebraic description of connectivity. (math.mit.edu)
Graph models separate relationships from irrelevant geometric detail. Road vertices can represent junctions, molecular vertices can represent atoms, and puzzle vertices can represent configurations. Algebraic and spectral methods also support random walks, network partitioning, electrical-network analysis, and web-search methods. The same underlying graph may therefore be investigated through combinatorial arguments, numerical matrices, or computational procedures, depending on the question being asked. (web.math.princeton.edu)