Graph theory is the branch of mathematics that examines the properties of graphs. See glossary of graph theory for common terms and their definition.

Informally, a graph is a set of objects called vertices (or nodes) connected by links called edges (or arcs). Typically, a graph is depicted as a set of dots (i.e., vertices) connected by lines (i.e., edges).

Subcategories

There are 7 subcategories to this category.

Algebraic graph theory G Graph algorithms

G cont. Graph coloring Graphs N Networks

T Topological graph theory Trees (structure)

Articles in category "Graph theory"

There are 109 articles in this category.

Abstract semantic graph Adjacency list Adjacency matrix Admittance matrix Arc-transitive graph Augmenting path B Betti number Betweenness Biadjacency matrix Bottleneck traveling salesman problem C Cayley's formula Centrality Circuit Rank Clique (graph theory) Clique problem Closeness (graph theory) Clustering coefficient Cograph Col game Complement (graph theory) Complex network Connected component (graph theory) Connectivity (graph theory) Covering (graph theory) Critical graph Crossing number Cycle decomposition D Degree (graph theory) Degree (mathematics) Degree matrix Discrete Laplace operator Distance (graph theory) Domatic number Domatic number problem Dominating set Dominating set problem

E Erdos-Faber-Lovász conjecture Erdos-Gyárfás conjecture Eulerian path Extremal graph theory G Genus (mathematics) Girth Glossary of graph theory Graph (data structure) Graph (mathematics) Graph coloring Graph drawing Graph homomorphism Graph invariant Graph labeling Graph rewriting Graph theory H Hadwiger conjecture (graph theory) Hamiltonian path Hamiltonian path problem Heawood graph Homeomorphism (graph theory) Hypergraph I Incidence matrix Independent set Independent set problem K K-minimum spanning tree Kirchhoff's theorem Knight's Tour L Labeled multigraph Level structure Levi graph List of graph theory topics M Mac Lane's planarity criterion Matching Max flow min cut theorem Menger's theorem Metric dimension (graph theory)

M cont. Minimum spanning tree Minor (graph theory) N Net flow Network Network analysis Network flow O Open Shortest Path First P Path (graph theory) Prüfer sequence Q Quiver (mathematics) R Ramsey's theorem Reconstruction conjecture Robertson-Seymour theorem Rooted graph Rooted product (graph theory) Route inspection problem S Scale-free network Seven Bridges of Königsberg Shortest path problem Small-world network Snark (graph theory) Spanning tree (mathematics) Spring-based algorithm Steiner points Steiner tree Subgraph isomorphism problem Symmetric graph T Tait's conjecture Topological graph theory Toroidal graph Traveling salesman problem Tree decomposition Turán's theorem Tutte theorem V Vickrey-Clarke-Groves Visibility graph