Rank (graph theory)

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.

A sample graph and matrix: (corresponding to the four edges, e1–e4):

{\displaystyle {\begin{pmatrix}0&1&1&1\\1&0&0&0\\1&0&0&1\\1&0&1&0\\\end{pmatrix}}.}

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