Vertex

Definition

Vertex

A vertex is a fundamental unit in graph theory, representing an individual point where two or more edges meet in a graph.

The number of vertices of a graph can be denoted as or .

Neighbours

Undirected Neighbours

The set of adjacent vertices of a vertex in an undirected graph is denoted as:

The number of neighbours is given by:

Directed Neighbours

The set of successors of a vertex in a directed graph is given by:

The set of predecessors of a vertex in a directed graph is given by:

The number of successors and predecessors is given by:

Degree

Degree

The degree of a vertex is the number of neighbours of :

The minimum degree of a graph is the smallest degree of any vertex in :

The maximum degree of a graph is the largest degree of any vertex in :

Adjacency Matrix

Definition

Adjacency Matrix

An adjacency matrix is a square matrix used to represent a finite graph . For a graph with vertices, the adjacency matrix is defined such that:

Link to original