Introduction to Graph Theory

Vertex

Denoted by a point.

Degree

The number of edges incident on a vertex. Denoted by $\text{deg}(v)$. A loop contributes 2 to the degree of a vertex.

Isolated Vertex

When a vertex’s degree is 0.

Pendant Vertex

When a vertex’s degree is 1.

Degree Sequence

The list of its vertex degrees sorted in descending order.

Edge

Denoted by a line.

Loop

An edge that connects a vertex to itself. Contributes 2 to total degree.

Multi-edge

More than one edge connecting 2 vertices.

Pseudograph

A pseudograph consists of a set of vertices ($V$) and some pairs of these are connected by edges ($E$). Denoted as $G=(V,E)$.

For all the definitions below, consider a graph $G$ with non-empty vertex set $V$ and edge set $E$.

2 types:

• Multigraph
  May include multi-edges or loops.
• Simple graph

Adjacency

Two vertices are said to be adjacent iff they are connected by an edge.

Two edges are said to be adjacent iff they share a common vertex.

Incidence

An edge is said to be incident to a vertex iff the vertex is one of the endpoints of the edge.

A vertex is said to be incident to an edge iff the edge is one of the edges connected to the vertex.

Subgraph

Suppose $G' = (V', E')$ and $G = (V, E)$.

If $V' \subseteq V$ and $E' \subseteq E$ then $G'$ is a subgraph of $G$.

Supergraph

In the above example, $G$ is a supergraph of $G'$.