Graph Theory Terminology

Graph

A non-empty set of vertices and edges connecting vertices

Parallel Edges

Two edges that have the same end vertices

Loop

An edge that connects a vertex to itself

Simple Graph

A graph that does not contain parallel edges or loops

End Vertex

A vertex at one of the endpoints of an edge in a graph

Empty Graph

A graph that contains no edges

Null Graph

A graph with no vertices and no edges

Trivial Graph

A graph with a single vertex and no edges

Adjacent Edges

Two edges that share a common vertex

Adjacent Vertices

Two vertices that are connected by an edge

Deg

d(V)

the number of edges connected to a vertex, loops are counted twice

Pendant Vertex

a vertex connected to exactly one edge

Pendant Edge

an edge that connects a pendant vertex to the rest of the graph.

s(G)

The minimumdegree of any vertex in graph G

Δ(G)

The maximum degree of any vertex in graph G

Complete Graph - K(n)

A simple graph in which every vertex is connected/adjacent to all other vertices

Cycle Graph - C(n)

A simple graph that is a cycle with n vertices (n >2). Each vertex has degree 2.

Wheel Graph - W(n)

A graph formed by connecting a single central vertex to all vertices of a cycle graph C(n) with n vertices, resulting in n+1 vertices in total.

Bipartite Graph

A graph whose vertices can be divided into two disjoint and independent sets such that every edge connects a vertex in one set to a vertex in the other set.

Complementary Graph

The graph formed by replacing the edges of a graph with non-edges and the non-edges with edges, while keeping the same set of vertices

Walk

A sequence of vertices and edges that helps us to travel from an initial vertex to a terminal vertex in a graph

Terminal Vertex

A vertex with no outgoing edges, marking the end of a walk in a graph

Initial Vertex

The starting point of a walk in a graph, where the traversal begins

Trail

A walk in which all edges are distinct, meaning no edge is traversed more than once.

Circuit

A closed trail in a graph where the starting and ending vertices are the same, and all edges are distinct.

Path

A walk in a graph where all vertices are distinct, meaning no vertex is visited more than once.

Cycle

A closed path in a graph where the starting and ending vertices are the same, and all vertices are distinct.

Circuitless Graph

A graph with no loops & there is at most one path between any two vertices

Cut Vertex

A vertex in a graph whose removal increases the number of connected components, effectively disconnecting the graph.

Cut Edge

An edge in a graph whose removal increases the number of connected components, effectively disconnecting the graph.

Euler Walk

A walk in a graph that visits every edge exactly once and may repeat vertices.

Euler Circuit

An Euler walk that starts and ends at the same vertex, visiting every edge exactly once.

Hamiltonian Cycle

A cycle in a graph that visits every vertex exactly once and returns to the starting vertex.

Hamiltonian Path

A path in a graph that visits every vertex exactly once without necessarily returning to the starting vertex.

Dirac’s Theorem

States that in a graph of n vertices (n ≥ 3), if each vertex has a degree of at least n/2, then the graph contains a Hamiltonian cycle.

Ores Theorem

States that any graph with n vertices (n ≥ 3) that contains no K{3,3} or K{5} subgraphs is Hamiltonian.

Tree

A connected acyclic graph that has no cycles and any two vertices are connected by exactly one path.

Trivial Tree

A tree with only one vertex and no edges, which is a special case of a tree.

Forest

A disjoint union of trees, where each component is a tree and there are no cycles.

Rooted Tree

A tree in which one vertex is designated as the root, and every other vertex has a unique parent, thus establishing a hierarchical structure.

Height

The length of the longest path from the root to a leaf in a tree.

Internal Vertex

A vertex in a tree that has at least one child, meaning it is not a leaf.

Leaf

A vertex in a tree that has no children, meaning it is at the end of a path.