Graph theory

A graph consists of a set of vertices (also called nodes) and a set of edges that connect selected pairs of vertices. The vertices might stand for places, people, tasks or web pages; an edge records a relationship chosen for the problem being studied. A graph is an abstract structure: its meaning comes from which vertices are connected, not from how a diagram is laid out or how far apart its points appear. This makes the same graph drawable in many different ways.

In an undirected graph, an edge represents a two-way relationship; in a directed graph, each edge has an orientation, as when one web page links to another. A weighted graph associates a value such as distance, cost or capacity with an edge. Other useful distinctions include whether every pair of vertices is connected by an edge, whether there are multiple edges between two vertices, and whether the graph is connected by paths. These choices are part of the model, so a graph is only as informative as the relationships and attributes it records.

A landmark in the subject arose from a puzzle about whether a person could cross each of the seven bridges in Königsberg exactly once. In 1736, Leonhard Euler treated each land region as a vertex and each bridge as an edge, turning a question about a walk through a city into a question about a graph. The resulting graph had four vertices of odd degree. A connected graph has a walk that uses each edge exactly once only when it has zero or two odd-degree vertices, so no such route existed. Euler's solution showed how the pattern of connections could settle the question without measuring the bridges or plotting a particular route; it became a foundation for graph theory.

The field studies both the structure of graphs and procedures for solving problems represented by them. A shortest-path problem asks for the least-cost route between vertices; a matching problem seeks compatible pairings, such as assigning applicants to available positions; and a coloring problem gives neighboring vertices different labels, which can represent conflict-free exam times or radio frequencies. A spanning tree connects all vertices of a connected graph without cycles; in a weighted graph, a minimum spanning tree minimizes the total edge weight and can help plan a low-cost network. Such models do not automatically reproduce every detail of the real world: the analyst must decide which relationships matter and what information to encode.

Graph theory connects discrete mathematics with computer science and applied work on networks. Its basic language is deliberately flexible: a single set of vertices and edges can describe a social relationship, a transport system, a communication link or a scheduling conflict, while different graph types capture direction, multiplicity or cost. Researchers study general theorems about these structures as well as algorithms for large, practical instances. The model's simplicity is powerful, but interpreting its results requires keeping the original question and assumptions in view.