# Glossary of graph theoretic terms

This page provides a reference for graph theory related terms that may appear on this wiki.

## A

Two vertices, u  and v , are adjacent in a graph if (u , v ) is an edge in that graph. Alternatively there is an edge incident on both u  and v .
${\displaystyle n}$-arc
A walk of n  vertices where any repeated vertices are three or more steps apart.
${\displaystyle n}$-arc-transitive graph
A graph whose automorphism group acts transitively on n -arcs. 1-arc-transitive graphs are also called flag-transitive.
Articulation point
A vertex of a connected graph which when removed along with all incident edges causes the graph to become disconnected.

## B

Biclique
A bipartite graph with two parts A  and B , such that every vertex in A  is adjacent to every vertex in B . If A  has n  vertices and B  has m  vertices then the biclique is denoted ${\displaystyle K_{3,5}}$.
Bipartite
A graph with two sets of vertices A  and B , called parts, such that no vertex in A  is adjacent to a vertex in A , and no vertex in B  is adjacent to a vertex in B . Alternatively a graph with a vertex 2-coloring.
Buckle
See § loop

## C

Claw
The star graph ${\displaystyle S_{3}}$.
Clique
A complete subgraph.
${\displaystyle C_{n}}$
The cyclic graph with n  vertices.
Complete graph
A graph where every pair of its vertices is an edge.
Complete ${\displaystyle k}$-partite graph
A k -partite graph where every pair of vertices in different parts is an edge.
Connected graph
A graph is connected iff there is a path between every pair of vertices.
Cubic graph
A regular graph with vertex degree 3.
Cycle
A non-empty trail with an equal start and end vertex. Two cycles are generally considered the same if they have the same vertices regardless of where they start or end.
Cyclic graph
A graph with exactly one cycle consisting of all of its vertices and edges

## D

Degree
The number of edges incident on a vertex is the degree of that vertex.
Disconnected graph
A graph which is not connected
Distance
The distance between two vertices in a graph is the length of the shortest path beginning at one and ending at the other.
Distance-transitive graph
A graph such that for any constant d  its automorphism group acts transitively on pairs of vertices, which are distance d  apart. Distance-transitive graphs have a high degree of symmetry, they are flag-transitive, vertex-transitive, edge-transitive, etc.

## E

Edge
One of the two basic elements of a graph. Edges connect vertices. In a simple graph edges are typically represented as an unordered pair of vertices.
Edge-colored graph
A graph with labeled edgeses such that if two edges are incident on a vertex they have different labels. A graph is n -edge-colored if its label set has size n .

## F

Flag
A vertex-edge pair (v , e ) where v  is one of the vertices of e . This is a special case of the flags of a poset for graphs and is analogous to the concept of flags on polytopes.
Flag graph
An edge-colored graph with vertices corresponding to the flags of a polytope.

Flag-transitive graph
A graph whose automorphism group acts transitively on its flags. This is analogous to the concept of abstract regular polytopes. However, unlike a regular polytope where the automorpism group and the flags set must have the same size, flag-transitive graph may have symmetry exceeding the number of automorphisms.

## G

Girth
The size of the smallest cycle of a graph.

## I

Incident
An edge ${\displaystyle (v_{1},v_{2})}$ is incident on v1  and v2  and no other vertices.

## K

${\displaystyle K_{n}}$
The complete graph with n  vertices.
${\displaystyle K_{n,m}}$
The biclique with with parts of size n  and m .

## L

Loop
An edge ${\displaystyle (u,v)}$ where ${\displaystyle u=v}$. Graphs with loops are not simple.

## M

Multiple edge
More than one edge between the same two vertices.

## P

Part
One of the sets of vertices in a k -partite graph with no internal connections.
${\displaystyle k}$-partite
A graph with k  sets of vertices, called parts, such that no vertex is adjacent to any vertex in the same part. Alternatively a graph with a vertex k -coloring.
Path
A walk in which all vertices are distinct. A path is also a trail.
Properly edge-colored graph
An n -edge-colored graph which is also n -regular.

## Q

${\displaystyle Q_{n}}$
The skeleton of the rank-n  hypercube.

## R

Regular graph
A graph in which every vertex has the same degree.

## S

Self-loop
See § loop
Simple graph
A simple graph is an undirected graph with at most 1 edge between and two vertices and no loops. In some context all graphs are implied to be simple.
${\displaystyle S_{n}}$
A star graph with ${\displaystyle n+1}$ vertices.
Star graph
A complete bipartite graph in which one of the parts has one vertex. The star graph with ${\displaystyle n+1}$ vertices is denoted ${\displaystyle S_{n}}$. Alternatively, ${\displaystyle S_{n}=K_{1,n}}$.
Subgraph
A subgraph of a graph G  is a graph formed from a subset of the vertices and edges of G . The subgraph must also be a valid graph so the endpoints of every edge must be included.
Symmetric graph
See § Flag-transitive graph

## T

Trail
A walk in which all edges are distinct.

## V

Vertex
One of the two basic elements of a graph. Vertices are connected by edges.
Vertex-colored graph
A graph with labeled vertices such that no two adjacent vertices share the same label. A graph is n -vertex-colored if its label set has size n .

## W

Walk
A sequence of edges, ${\displaystyle \{e\}_{i}}$, and a sequence of vertices, ${\displaystyle \{v\}_{i+1}}$, of a graph, such that ${\displaystyle e_{i}=(v_{i},v_{i+1})}$.