Graph Theory - definitions, relationships

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.