Graph Theory

Graph

a non-empty set of edges and vertices.

Simple Graph

a graph that does not contain any loops or parallel edges.

Complete Graph

A simple graph that contains all possible edges between every pair of vertices.

Cycle Graph

A graph with n vertices that only has edges its circumference.

Wheel Graph

A cycle graph with an additional vertex connected to every other vertex

Bipartite Graph

A graph that can be partitioned into two sets v1 and v2.

Complete Bipartite Graph

A Bipartite graph that includes all possible edges between vertices in v2 and vertices in v1.

Walk

A finite sequence of vertices and edges.

Closed Walk/ Cycle

A finite sequence of vertices and edges that travels to the same place.

Trial

A walk with no repeated edges.

Path

A walk with no repeated vertices and edges except for its initial and terminal vertices.

Circuit

A closed path.

Connected Graph

A graph that has a walk between each pair of vertices.

Cut Vertex

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

Cut Edge

Edge whose removal increases the number of connected components in a graph.

Euler Walk

A walk that uses every edge exactly once.

Euler Circuit

A closed walk that uses each edge exactly once.

Hamiltonian Circuit

A circuit that uses every vertex in a graph exactly once.

Hamiltonian Path

A path that uses every vertex in a graph exactly once 

Euler Theorem

A connected graph G has an Euler circuit if and only if every vertex has an even degree. If it has an Euler walk, it cannot have an Euler circuit.

Hamilton Theorem

If G is a simple graph with n vertices, n>3, and d(V) + d(W) >= n where V and W are not adjacent, then G has a Hamiltonian Circuit.