Graph Theory - definitions, relationships

Home Algebra Geometry Mathematical analysis Probability and Statistics

Graph is made up of vertices, which are connected by edges.


The degree of the vertex, is the number of edges of that vertex.
(By convention, we count a loop twice and parallel edges contribute separately)

For a vertex, the number of head ends adjacent to a vertex is called the indegree of the vertex and the number of tail ends adjacent to a vertex is its outdegree.

Regular graph is a graph where each vertex has the same degree.

Edges that have the same end vertices are parallel.

Loop is an edge that connects a vertex to itself.

An isolated vertex is a vertex whose degree is 0 (no vertices).

A graph with no edges is an empty grpaph.

A graph is simple if it has no parallel edges or loops.

A simple graph that contains every possible edge between all the vertices is called a complete graph.


A planar graph is a graph that can be embedded in the plane (no crossing vertices).


A walk: is a sequence whose terms alternate between vertices and edges (not necessarily distinct).
A trail is a walk such that all of the edges are distinct.
A path is a trail with no repeated vertex.
A cycle is a closed path.


A graph is connected when there is a path between every pair of vertices.


Eulerian trail (or Eulerian path) is a trail which visits every edge exactly once.
Hamiltonian path is a path that visits each vertex exactly once.
Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle.


A tree is an undirected graph in which any two vertices are connected by exactly one path.
Number of vertices=number of edges+1

Forest: every component is a tree.
Number of vertices=number of edges+number of components.


Home Algebra Geometry Mathematical analysis Probability and Statistics