Graphs and Associated Terminology

Vocabulary and formulas related to graph theory, including vertex properties, graph types, and connection rules.

Graph

A diagram that shows connections between people or objects, such as towns connected by roads or people on social media.

Vertex

A dot in a graph representing an object, person, or city; the plural form is vertices.

Edge

A line that joins pairs of vertices to represent the connection between them.

Multiple edges

A feature where two or more edges connect the same two vertices in a graph.

Simple graph

A graph that has no loops and no duplicate or multiple edges.

Isolated vertex

A vertex that is not connected to any other vertex by an edge, resulting in a degree of $0$.

Degenerate graph

A graph where all vertices are isolated, meaning there are no edges in the graph at all.

Connected graph

A graph where every vertex is connected to every other vertex, either directly or indirectly via other vertices.

Bridge

An edge in a connected graph that, if removed, will cause the graph to become disconnected.

Complete graph

A graph where every vertex is connected directly by an edge to every other vertex in the graph.

Degree of a vertex in a complete graph

One less than the number of vertices, represented as $n - 1$.

Number of edges in a complete graph

For a complete graph with $n$ vertices, the formula is $\frac{1}{2} \times n \times (n - 1)$.

Subgraph

A part of a larger graph where all of its edges and vertices must exist in the original graph.

Loop

An edge that connects a vertex to itself, adding $2$ to the degree of that vertex.

Degree of a vertex

The number of times an edge connects to a vertex, written as $\text{deg}(V)$.

Even vertex

A vertex where the degree of the vertex is an even number.

Odd vertex

A vertex where the degree of the vertex is an odd number.

Sum of degrees

The total value of all vertex degrees in a graph, which is equal to $2$ times the number of edges.

Eulers formula

V + f - e = 2

Walk

A route path through a graph from one vertex to another along the edges of a graph

Open walk

A walk that starts and ends at different vertices

Trail

A walk that has no repeated edges but can repeat vertices

Path

A walk with no repeated edges or vertices

Closed trail

A trail that starts and ends at the same vertex

Cycle

A path that starts and ends at the same vertex

Eulerian trail

A closed trail that involves every edge of the graph, where every vertex must have an even degree

Eulerian graph

A graph that contains an Eulerian trail

Semi Eulerian graph

A graph that contains an open trail that involves every edge of the graph and has two vertices eith an odd degree

Hamiltonian cycle

A closed path that visits every vertex of the graph and starts and ends in the same place

Hamiltonian path

An open path that visits every vertex of the graph

Semi-Hamiltonian path

A graph that contains an Eulerian Hamiltonian path

Weighted graph

A graph that has numbers associated with each edge of the graph

Network

A weighted graph that represents physical quantities ( e.g time, distance, cost, ect. )

The travelling salesperson problem

Finding a Hamiltonian cycle in a graph that has the smallest total weight ( uses key phrases/words such as minimising the total distance travelled through a graph to return to the start vertex …)

The shortest path problem

Finding the shortest path from one vertex to another, but does not have to visit every vertex

Planar

A graph where all vertices are connected but none cross over each other