+- MKLab (https://mklab.gr)
+-- Forum: [INDEX] (https://mklab.gr/forumdisplay.php?fid=1)
+--- Forum: MATHEMATICS (https://mklab.gr/forumdisplay.php?fid=3)
+---- Forum: ARTICLES (https://mklab.gr/forumdisplay.php?fid=13)
+----- Forum: GRAPHS AND NETWORKS (https://mklab.gr/forumdisplay.php?fid=202)
+----- Thread: Graph theory (/showthread.php?tid=2196)
Graph theory - mklabgr - 09-25-2026
Graph theory is a branch of discrete mathematics concerned with mathematical structures called graphs, which model relationships between objects. A graph consists of vertices (or nodes) and edges connecting pairs of vertices. In an undirected graph, an edge represents a symmetric relationship, while in a directed graph, each edge has an orientation. Graphs can also be weighted, allowing edges to carry numerical values such as distances or costs, and multigraphs can contain multiple edges between the same pair of vertices or loops.
The origins of graph theory are usually traced to Euler's 1736 solution of the Seven Bridges of Königsberg problem, which demonstrated how a spatial problem could be transformed into an abstract network problem. Since then, the subject has developed into a major mathematical field, with important connections to combinatorics, topology, algebra, geometry, probability, and computer science. Classic problems such as the Four Color Theorem, questions about Eulerian and Hamiltonian paths, and the enumeration of trees helped establish many of the central ideas of the discipline.
A central concern is understanding the structure and properties of graphs. Important concepts include paths, cycles, connectivity, trees, bipartite graphs, planar graphs, graph coloring, and graph matching. For example, the degree of a vertex measures how many edges are incident to it, while the chromatic number $\chi(G)$ is the minimum number of colors needed to color the vertices so that adjacent vertices receive different colors. Graphs can also be represented algebraically through an adjacency matrix $A$, while the graph Laplacian is commonly defined as $L=D-A$, where $D$ is the diagonal degree matrix.
Graph theory has become fundamental far beyond pure mathematics. It provides mathematical models for computer networks, transportation systems, social networks, biological interactions, chemical structures, communication networks, cybersecurity, scheduling, and optimization. Problems such as finding shortest paths, constructing minimum spanning trees, determining network flows, and detecting communities can all be expressed using graphs. Modern graph theory also includes specialized areas such as algebraic/spectral graph theory, topological graph theory, geometric graph theory, extremal graph theory, random graph theory, and graph enumeration, making it an important bridge between theoretical mathematics and real-world computational problems.
Key Takeaways
- Graph: $G=(V,E)$, where $V$ is the set of vertices and $E$ is the set of edges.
- Degree of a vertex: $\deg(v)$ = number of edges incident to $v$.
- Handshake Lemma: $\displaystyle \sum_{v\in V}\deg(v)=2|E|$.
- Path: a sequence of vertices connected by edges.
- Cycle: a path that returns to its starting vertex.
- Connected graph: every pair of vertices has a path between them.
- Tree: a connected graph with no cycles; a tree with $n$ vertices has exactly $n-1$ edges.
- Complete graph: $K_n$ has $\displaystyle \frac{n(n-1)}{2}$ edges.
- Graph coloring: adjacent vertices must receive different colors.
- Chromatic number: $\chi(G)$ is the minimum number of colors required.
- Adjacency matrix: $A_{ij}=1$ when vertices $i$ and $j$ are adjacent, and $0$ otherwise.
- Graph Laplacian: $L=D-A$.
- Eulerian problems: concern traversing every edge exactly once.
- Hamiltonian problems: concern visiting every vertex exactly once.
- Shortest-path problems: minimize the total weight along a path.
- Minimum spanning tree: connects all vertices while minimizing total edge weight.
- Graph theory provides a powerful mathematical language for networks and relationships.
- Its applications range from pure mathematics to AI, algorithms, cybersecurity, biology, physics, and social-network analysis.
ARTICLE / PDF