Glossary of graph theory

Graph theory is a fascinating area of mathematics that studies connections between objects. It looks at how things — called nodes or vertices — can be linked together by edges, which are like lines or paths connecting the nodes.

Graphs help us understand many real-world problems, like finding the quickest route on a map or designing strong networks for computers and phones. By using simple pictures made of dots and lines, graph theory can solve complex puzzles about connections and relationships.

This glossary explains important terms and ideas used in graph theory. Whether you're curious about how networks work or just love solving puzzles, graph theory offers fun and useful ways to think about the world around us.

Symbols

Square brackets [ ] are used to show an induced subgraph of a graph. For example, _G__S_ refers to a smaller part of a bigger graph.

The [prime symbol ' helps us talk about different properties of graphs. For example, _α_(G_) tells us about one property of a graph, while _α_′(G_) tells us about a related property of its line graph.

A

In graph theory, an absorbing set is a group of points in a directed graph where every other point has a connection leading to this set.

An acyclic graph is one that has no cycles. For undirected graphs, this means it is a type of forest, while in directed graphs, it is known as a directed acyclic graph.

The adjacency matrix shows connections between points in a graph, with a 1 indicating a connection and a 0 showing no connection.

Other terms like adjacent describe points or lines that connect directly, while alternating paths switch between connected and unconnected lines in matchings.

B

A bipartite graph is a graph whose vertices can be divided into two groups. Vertices in one group connect only to vertices in the other group, not to each other. These graphs have no odd-length cycles and can be colored with just two colors.

Other terms include biconnected, which describes a graph where there are at least two separate ways to travel between any pair of points, and bridge, an edge that if removed would split the graph into separate parts.

C

C_n is an n-vertex cycle graph.

A cactus graph is a connected graph in which each edge belongs to at most one cycle.

A cage is a regular graph with the smallest possible order for its girth.

A canonical form of a graph is an invariant such that two graphs have equal invariants if and only if they are isomorphic. Graph canonization is the process of computing a canonical form.

A graph formed from a given graph by deleting one vertex is called a card, especially in the context of the reconstruction conjecture.

Carving width is a notion of graph width similar to branchwidth.

A caterpillar tree is a tree in which the internal nodes form a path.

The center of a graph is the set of vertices of minimum eccentricity.

In a rooted tree, a child of a vertex v is a neighbor of v along an outgoing edge.

A chord of a cycle is an edge that does not belong to the cycle, for which both endpoints belong to the cycle.

Chromatic graph theory deals with graph coloring. The chromatic number χ(G) is the minimum number of colors needed in a proper coloring of G.

A graph is k-choosable if it has a list coloring whenever each vertex has a list of k available colors.

A circle graph is the intersection graph of chords of a circle.

A circuit may refer to a closed trail or an element of the cycle space. The circuit rank of a graph is the dimension of its cycle space.

The circumference of a graph is the length of its longest simple cycle.

A class of graphs is a collection of graphs, often defined by some specific property.

A claw is a tree with one internal vertex and three leaves.

A clique is a set of mutually adjacent vertices. The clique number ω(G) of a graph G is the order of its largest clique.

A connected component of a graph is a maximal connected subgraph.

A connected graph is one in which each pair of vertices forms the endpoints of a path.

Edge contraction is an operation that removes an edge from a graph while merging the two vertices that it previously joined.

The converse graph is a synonym for the transpose graph.

A k-core is the induced subgraph formed by removing all vertices of degree less than k.

A cube graph is the eight-vertex graph of the vertices and edges of a cube.

A cut is a partition of the vertices of a graph into two subsets, or the set of edges that span such a partition.

A cycle may be a kind of graph or a kind of walk. As a walk it may be a closed walk, or more usually a closed walk without repeated vertices and consequently edges. Important special types of cycle include Hamiltonian cycles and the shortest cycle, which defines the girth of a graph. A k-cycle is a cycle of length k. A cycle graph is a graph that is itself a simple cycle.

D

A directed acyclic graph (or DAG) is a type of directed graph that has no cycles — it only goes in one direction and never loops back on itself directed acyclic graph.

Other important terms in graph theory include:

• Deck: This is a collection of graphs created by removing one vertex at a time from a larger graph, often used to study how well we can guess the original graph reconstruction conjecture.
• Degeneracy: This describes how "complex" a graph is. A graph is k-degenerate if every smaller part of it has at most k connections leaving each point degeneracy.
• Degree: This counts how many connections (edges) a point (vertex) has. The degree of a graph is the most connections any single point has handshaking lemma.
• Density: This measures how many connections exist compared to the maximum possible. A dense graph has many connections, while a sparse graph has few dense graph.
• Diameter: This is the longest shortest path between any two points in a connected graph diameter.
• Diamond graph: A small graph with four points and five connections diamond graph.
• Digraph: Short for directed graph, where each connection has a specific direction directed graph.
• Distance: The fewest steps needed to go from one point to another in a graph distance.
• Dominating set: A group of points where every other point is either in the group or directly connected to someone in the group dominating set.
• Dual graph: For a graph drawn on a plane, the dual graph has a point for each space between lines dual graph.

E

E

E(G) is the edge set of G; see edge set.

In graph theory, an ear of a graph is a path where the ends may be the same, but no other points repeat. An ear decomposition breaks down the edges of a graph into a sequence of these ears.

The eccentricity of a vertex tells us how far it is from the most distant vertex in the graph.

An edge is one of the main parts of a graph, connecting two vertices. Edges can go in one direction or both directions.

An edge cut is a group of edges that, if removed, would split the graph apart. A single edge that does this is called a bridge.

The edge set is simply all the edges in a graph.

An edgeless graph is a graph with no edges at all — just vertices standing alone.

A graph embedding shows a graph as points (vertices) and curves (edges) in space, without any curves crossing. A planar graph can be drawn on a flat surface, while a toroidal graph can be drawn on a donut shape.

The empty graph has either just vertices with no edges, or no vertices and no edges at all.

An endpoint is one of the vertices where an edge starts or ends. For a directed edge, the starting point is called the tail, and the ending point is the head.

Graph enumeration is about counting different kinds of graphs or structures within graphs, like how many ways you can color the vertices.

An Eulerian path is a path that uses every edge of a graph exactly once. If it starts and ends at the same vertex, it’s called an Eulerian circuit. A graph that can have such a circuit is Eulerian.

An even number is divisible by two — for example, an even cycle has an even number of vertices.

An expander graph is a graph where spreading out its edges or vertices doesn’t shrink the graph too much. This helps in studying how networks grow and connect.

F

In graph theory, a face is a part of a plane or surface that is not covered by the lines or edges of the graph. When the graph is drawn on a flat surface, most faces are surrounded by edges, but one special face reaches out to infinity and is called the outer face.

A factor of a graph is a smaller graph that includes all the points (vertices) of the original graph. Special types of factors are named based on how many connections (edges) each point has. For example, a 1-factor is the same as pairing up all the points so each is connected to exactly one other point.

G

G

This letter is often used to represent a graph.

genus

The genus of a graph tells us the simplest surface needed to draw the graph without any edges crossing.

geodesic

A geodesic is another name for the shortest path between two points in a graph.

giant

In studies of random graphs, a giant component is a large connected part that includes a steady portion of all the points in the graph.

girth

The girth of a graph is the number of steps in its smallest loop.

graph

A graph is the main object studied in graph theory. It consists of points, called vertices, connected by lines, called edges. Graphs can be directed, where edges have a direction, or undirected, where they do not. Mixed graphs have both types of edges.

greedy

A greedy algorithm makes the best choice at each step. For example, a greedy coloring of a graph assigns the first available color to each vertex in order.

Grötzsch

1. Herbert Grötzsch
2. The Grötzsch graph, a special graph that has no triangles but still needs four colors to color it properly.
3. Grötzsch's theorem shows that triangle-free planar graphs can always be colored using only three colors.

Grundy number

The Grundy number of a graph is the most colors you might need when coloring it using a greedy method, depending on the order you choose the vertices.

H

H

H often represents a graph, especially when another graph is already called G.

H-coloring

An H-coloring of a graph G (where H is also a graph) is a special mapping from H to G.

H-free

A graph is H-free if it does not contain a certain smaller graph H inside it. For example, triangle-free graphs are graphs that do not have a triangle graph inside them.

Hadwiger

1. Hugo Hadwiger
2. The Hadwiger number of a graph is the size of the largest complete minor of the graph.
3. The Hadwiger conjecture suggests that the Hadwiger number is never smaller than the chromatic number.

Hamiltonian

A Hamiltonian path or Hamiltonian cycle is a path or cycle that visits each vertex in the graph exactly once. A graph is Hamiltonian if it contains a Hamiltonian cycle, and traceable if it contains a Hamiltonian path.

haven

A k-haven is a special function used to study the structure of graphs.

height

The height of a node in a tree is the number of edges in the longest path from that node to a leaf. The height of a tree is the height of its root node.

hereditary

A hereditary property of graphs is a property that remains true for all smaller parts of the graph.

hexagon

A simple cycle with exactly six edges and six vertices.

hole

A hole is a special cycle in a graph with four or more vertices. This idea is important in the study of perfect graphs, described by the strong perfect graph theorem. Hole-free graphs are the same as chordal graphs.

homomorphic equivalence

Two graphs are homomorphically equivalent if there are special mappings between them.

homomorphism

A graph homomorphism is a mapping between the vertices of two graphs that keeps connections between vertices. It is used in many graph theory studies.

hyperarc

A directed hyperedge with a starting point and an ending set.

hyperedge

An edge in a hypergraph, which can connect to more than two points, unlike normal graph edges.

hypercube

A hypercube graph is a graph made from the vertices and edges of a geometric hypercube.

hypergraph

A hypergraph is a more general type of graph where edges can connect to more than two points.

hypo-

This prefix describes a graph that lacks a certain property, but becomes true when any single vertex is removed. For example, a hypohamiltonian graph does not have a Hamiltonian cycle, but removing any one vertex makes it have one.

I

The "in-degree" of a directed graph counts how many edges point toward each vertex. An "incidence" describes a vertex connected to an edge.

An "incidence matrix" is a table that shows which vertices connect to which edges, using ones and zeros. An "independent set" is a group of vertices with no edges between them.

An "induced subgraph" includes all edges between a chosen group of vertices. An "infinite graph" has endless vertices or edges.

An "isolated vertex" has no edges connected to it at all. Two graphs are "isomorphic" if they have the same structure, just arranged differently.

J

The join of two graphs is made by connecting every point, or vertex, from one graph to every point in the other graph. This is done after placing the two graphs apart from each other, and then linking each point in one graph to each point in the other graph.

K

K

The notation K is used to describe special types of graphs called complete graphs, complete bipartite graphs, and complete multipartite graphs. You can learn more about complete graphs here.

κ

κ(G), using the Greek letter kappa, can mean two things depending on the context. It might refer to the vertex connectivity of a graph G, or it could represent the clique number of G. You can find out more about vertex connectivity here and clique numbers here.

kernel

In a directed graph, a kernel is a special set of vertices that is both stable and absorbing.

knot

A knot in graph theory is an inescapable part of a directed graph. To learn more, you can explore knot (mathematics) and knot theory.

L

L

L(G) is the line graph of G; see line.

label

A labeled graph is a graph whose vertices or edges have labels. The terms vertex-labeled or edge-labeled may be used to specify which objects of a graph have labels. Graph labeling refers to several different problems of assigning labels to graphs subject to certain constraints. See also graph coloring.

leaf

A leaf vertex or pendant vertex (especially in a tree) is a vertex whose degree is 1. A leaf edge or pendant edge is the edge connecting a leaf vertex to its single neighbour.

length

In an unweighted graph, the length of a cycle, path, or walk is the number of edges it uses. In a weighted graph, it may instead be the sum of the weights of the edges that it uses. Length is used to define the shortest path, girth (shortest cycle length), and longest path between two vertices in a graph.

level

A node's level in a rooted tree is the number of nodes in the path from the root to the node. For instance, the root has level 1 and any one of its adjacent nodes has level 2.

line

A synonym for an undirected edge. The line graph L(G) of a graph G is a graph with a vertex for each edge of G and an edge for each pair of edges that share an endpoint in G.

linkage

A synonym for degeneracy.

list

An adjacency list is a computer representation of graphs for use in graph algorithms.

local

A local property of a graph is a property that is determined only by the neighbourhoods of the vertices in the graph.

loop

A loop or self-loop is an edge both of whose endpoints are the same vertex. It forms a cycle of length 1. These are not allowed in simple graphs.

M

In graph theory, a matching is a set of connections (edges) where no two share a point (vertex). A perfect matching links every point, while a maximum matching uses as many connections as possible.

A minor of a graph is made by removing points or connections, or by merging connections. Other terms like modular graph and multigraph describe special kinds of graphs with different rules about how points can be connected.

N

A neighbor or neighbour is a vertex (or point) that is directly connected to another vertex in a graph. The neighborhood of a vertex includes all the vertices directly connected to it. In graph theory, a lower-case n is often used to show the number of vertices (or points) in a graph. A network is a type of graph where extra details, like names, are linked to the points or connections. A node is another name for a vertex. A non-edge is a pair of vertices that are not connected. A null graph is the same as an empty graph, which has no vertices or edges at all.

A triangle is a cycle with three points. A trivial graph has either no points or just one point.

Turán graphs are special graphs with the most edges possible without certain cycles.

U

In graph theory, a unary vertex is a vertex in a rooted tree that has exactly one child vertex.

An undirected graph is a graph where the edges do not have a direction. This means the two points connected by an edge are the same, no matter which way you look at it. A universal graph is a special graph that contains every possible smaller graph. A universal vertex is a vertex connected to every other vertex in the graph, like in wheel graphs. An unweighted graph is a graph where the points and lines do not have numbers or "weights" assigned to them. The utility graph is a special type of graph known as a complete bipartite graph, often written as K_3,3.

V

See vertex set.

valency

Synonym for degree.

vertex

A vertex (plural vertices) is one of the two basic units, along with edges, that make up graphs. Vertices are often thought of as simple points with no internal structure.

vertex cut

separating set

A set of vertices that, when removed, can disconnect the graph. A single-vertex cut is called an articulation point or cut vertex.

vertex set

The set of vertices of a given graph G, sometimes written as V(G).

vertices

See vertex.

Vizing

1.  Vadim G. Vizing 2.  Vizing's theorem about the chromatic index. 3.  Vizing's conjecture on graph domination numbers.

volume

The sum of the degrees of a set of vertices.

W

The letter W is used in notation for wheel graphs and windmill graphs.

Wagner refers to several important ideas in graph theory:

1. Klaus Wagner, a mathematician who contributed to the field.
2. The Wagner graph, a special graph with eight points arranged in a certain way.
3. Wagner's theorem, which helps describe planar graphs by what they cannot contain.

A walk is a path that goes through a series of edges connecting vertices. Walks can be open (starting and ending at different points) or closed (starting and ending at the same point).

In graph theory, weight means a number assigned to a vertex or edge. A weighted graph is one where these points or lines have weights assigned to them.

A wheel graph is made by adding a central point, called a universal vertex, to a simple circle of points.

A windmill graph is formed by combining several groups of points (called cliques) that all share one common point.