Definitions Flashcards
Handshaking Lemma
The sum of the degrees of all the vertices in a graph is equal to twice the number of edges.
Bipartite graph
A graph whose vertices can be divided into two sets such that no two vertices in the
same set are adjacent.
Circuit
A walk that begins and ends at the same vertex, and has no repeated edges.
Complement of a graph G
A graph with the same vertices as G but which has an edge between any two
vertices if and only if G does not.
Complete bipartite
graph
A bipartite graph in which every vertex in one set is joined to every vertex in the
other set.
Complete graph
A simple graph in which each pair of vertices is joined by an edge.
Connected graph
A graph in which each pair of vertices is joined by a path.
Cycle
A walk that begins and ends at the same vertex, and has no other repeated vertices.
Degree of a vertex
The number of edges joined to the vertex; a loop contributes two edges, one for
each of its end points.
Disconnected graph
A graph that has at least one pair of vertices not joined by a path.
Eulerian circuit
A circuit that contains every edge of a graph.
Eulerian trail
A trail that contains every edge of a graph.
Graph
Consists of a set of vertices and a set of edges.
Graph isomorphism
between two simple
graphs G and H
A one-to-one correspondence between vertices of G and H such that a pair of
vertices in G is adjacent if and only if the corresponding pair in H is adjacent.
Hamiltonian cycle
A cycle that contains all the vertices of the graph.
Hamiltonian path
A path that contains all the vertices of the graph.
Loop
An edge joining a vertex to itself.
Minimum spanning
tree
A spanning tree of a weighted graph that has the minimum total weight.
Multiple edges
Occur if more than one edge joins the same pair of vertices.
Path
A walk with no repeated vertices.
Planar graph
A graph that can be drawn in the plane without any edge crossing another.
Simple graph
A graph without loops or multiple edges.
Spanning tree of a
graph
A subgraph that is a tree, containing every vertex of the graph.
Subgraph
A graph within a graph.
Trail
A walk in which no edge appears more than once.
Tree
A connected graph that contains no cycles.
Walk
A sequence of linked edges.
Weighted graph
A graph in which each edge is allocated a number or weight.
Weighted tree
A tree in which each edge is allocated a number or weight.
Chinese postman problem
To determine a cycle where each vertex is visited once only, returning to the original vertex of least total weight
Travelling salesman problem
To determine the shortest route that visits each vertex and returns to the original vertex, of least weight.
Pigeon Hole Principle
If kn+1 objects (where k, n are members of the positive integers) are divided into n groups, there will be a group that contains at least k+1 objects.
The Fundamental Theorem of Arithmetic
Every number >1 can be written as a unique product of prime numbers.
