In graph theory, a branch of mathematics, the rank of an undirected graph has two unrelated definitions. Let n equal the number of vertices of the graph. r of an undirected graph is defined as the rank of its adjacency matrix. n − r . n − c , where c 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. m − n + c , where n and c are as above and m is the number of edges in the graph. The nullity is equal to the first Betti number of the graph. The sum of the rank and the nullity is the number of edges.

Examples

A sample graph and matrix: (corresponding to the four edges, e1–e4): In this example, the matrix theory rank of the matrix is 4, because its column vectors are linearly independent.