graphtheory

Graph theory is the branch of mathematics that studies graphs, which are abstract structures consisting of vertices (or nodes) connected by edges. Graphs may be undirected or directed, weighted or unweighted, and may be simple or contain multiple edges and loops. They can be represented by adjacency matrices or adjacency lists, and by incidence relations between vertices and edges.

Basic objects include paths, chains of edges connecting vertices; cycles; connectivity (whether a path exists between two vertices); and degrees, the number of incident edges. Subgraphs are graphs contained within larger graphs; trees are connected acyclic graphs and form the basis of many algorithms; spanning trees connect all vertices with a minimal set of edges. Planar graphs can be drawn without edge crossings.

Graph theory encompasses fundamental results and algorithmic methods. Eulerian paths traverse each edge once; Hamiltonian paths traverse each vertex once. The four color theorem concerns coloring of planar graphs. Key algorithmic tools include breadth-first and depth-first search; shortest-path algorithms such as Dijkstra, Bellman-Ford, and Floyd-Warshall; and minimum spanning trees via Kruskal or Prim. Network flow problems are central in algorithmic graph theory, with the max-flow min-cut theorem appearing frequently.

Subfields include structural graph theory, which studies graph properties and forbidden subgraphs; algorithmic graph theory, which emphasizes compute methods; and spectral graph theory, which uses eigenvalues and eigenvectors of matrices associated with graphs, such as the adjacency and Laplacian matrices, to infer structure.

Applications span computer networks, transportation and logistics, social networks, biology and chemistry, and scheduling and resource allocation. Many graph problems are computationally hard; for example, finding a Hamiltonian cycle or determining a graph coloring with a fixed number of colors is NP-complete in general. Despite this, graph theory provides a unified framework for modeling and solving problems across disciplines.