Graph Theory Definitions

End vertices

two vertices connected by a specific edge

Parallel edges

edges with the same end vertices

Loop

an edge connecting a vertex to itself

Simple graph

a graph without parallel edges or loops

Empty graph

a graph with no edges

Null graph

a graph with no vertices

Trivial graph

a graph with only one vertex

adjacent edges

edges with a common end vertex

adjacent vertices

vertices connected by an edge

degree of a vertex

the number of edges connected to that vertex (loops are counted twice)

pendant vertex

a vertex with degree 1

pendant edge

an edge with a pendant vertex as an endpoint

isolated vertex

a vertex with degree 0

walk

a sequence of edges and vertices from an initial vertex to a terminal vertex

trail

a walk with no repeating edges

path

a walk with no repeating vertices (and edges)

closed walk

a walk from a vertex to itself

closed trail (circuit)

a trail from a vertex to itself

closed path (cycle)

a path from a vertex to itself

circuitless graph

a graph with no circuits

length of a walk

number of edges you go over to get to the terminal vertex

connected graph

a graph where all vertices are connected to each other

cut vertex

a vertex whose removal increases the number of connected components

cut edge

an edge whose removal increases the number of connected components

Euler walk

a walk that visits every edge exactly once

Euler circuit

a closed walk that visits every edge exactly once

Euler graph

a graph that has an Euler circuit

When does a graph have an Euler walk?

if it has exactly 2 vertices with an odd degree

When does a graph have an Euler circuit?

if every vertex has an even degree

Hamilton circuit

a circuit (closed walk) that visits every vertex exactly once

Hamilton path

a path that visits every vertex exactly once

Hamiltonian graph

a graph that has a Hamilton circuit

Dirac’s theorem

in a simple graph of n vertices, if the degree of each vertex is at least n/2, then the graph contains a Hamiltonian circuit

Ore’s theorem

in a simple graph of n vertices, if the degree of any two non-adjacent vertices sums to at least n, then the graph contains a Hamiltonian circuit

Complete graph (Kn)

a graph of n vertices, where each pair of vertices is connected by an edge

Cycle graph (Cn)

a graph of n vertices, where each vertex has a degree of 2 and are connected in a closed loop (edges follow “around” the graph)

Wheel graph (Wn)

a graph formed when adding a vertex to a cycle graph of n vertices (Cn) and connecting that vertex to all other vertices

Bipartite graph

a graph V whose vertices can be divided into two disjoint sets V1 and V2 such that every edge connects a vertex in V1 to one in V2

Complete bipartite graph (Km,n)

a bipartite graph that includes all possible edges between vertices in V1 and vertices in V2

When is a graph circuitless?

when there are no loops and there is at most one path between any two given vertices

When is a graph bipartite?

if it does not have a cycle of odd length

Tree

a connected graph with no circuits

Trivial Tree

a tree with one vertex

Forest

a graph that is circuit-free and not connected

rooted tree

a tree in which one vertex is designated as the root and every edge is away from the root

level of a vertex

number of edges you need to go over to get from that vertex to the root

height of a rooted tree

max level of any vertex of the tree

children of vertex v

all vertices that are adjacent to v and one level farther away from the root than v

internal vertices

vertices that have children

terminal vertex (leaf)

a vertex with no children

siblings

two distinct vertices that have the same parent

ancestors of a vertex

vertices on the path from the vertex to the root (including the root)

descendants of a vertex

vertices that have that vertex as an ancestor

m-ary tree

a rooted tree where every internal vertex has no more than m children

full m-ary tree

every internal vertex has exactly m children

What are the parts of a decision tree?

root nodes, internal nodes, and leaf nodes

How many edges does a tree with n vertices have?

A tree with n vertices has n - 1 edges