Eroxl's Notes
Graph (Discrete Mathematics)

A graph is a structure consisting of a pair of sets where is a set of vertices and is a set of edges where each is a pair of vertices .

Example of a graph with 5 vertices and 5 edges

Properties

Connectivity

Connectivity (Discrete Mathematics)

Connectivity describes whether vertices in a graph can reach each other through a sequence of edges.

Connected Graph

A graph is connected if there exists a path between every pair of vertices. In other words, you can travel from any vertex to any other vertex by following edges.

Formally, a graph is connected if for every pair of vertices , there exists a path from to .

Weakly Connected

In a directed graph, a graph is weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.

Strongly Connected

In a directed graph, a graph is strongly connected if there is a directed path from every vertex to every other vertex.

Sparsity

A graph is considered sparse if the number of edges is much less than the maximum number of possible edges. Conversely, a graph is dense if the number of edges is close to the maximum number of possible edges.

Formally, for a graph with vertices, a sparse graph has edges, while a dense graph has edges.

Variants