Rank (graph theory)

In graph theory, a branch of mathematics, the rank of an undirected graph has two unrelated definitions. Let equal the number of vertices of the graph.

In the matrix theory of graphs the rank of an undirected graph is defined as the rank of its adjacency matrix.
In the matroid theory of graphs the rank of an undirected graph is defined as the number, where is the number of connected components of the graph. Equivalently, the rank of a graph is the rank of the oriented incidence matrix associated with the graph.

Examples

A sample graph and matrix:
:

In this example, the matrix theory rank of the matrix is 4, because its column vectors are linearly independent.