Rank (graph theory) - Wikipedia

Abstraction: Two definitions of rank for undirected graphs via matrix and matroid theory

Key points:

• Matrix-theory definition: rank of an undirected graph equals the rank of its adjacency matrix; nullity equals n minus rank
• Matroid-theory definition: rank equals n - c, where n is vertices and c is number of connected components; equivalently, rank of the oriented incidence matrix
• Matroid nullity is m - n + c (m = edges), equal to the first Betti number; sum of rank and nullity equals number of edges
• The two definitions are unrelated despite both using the term "rank"

Connections: Graph Rank · Adjacency Matrix · Matroid Theory · Graph Connectivity

Source: http://en.wikipedia.org/wiki/Rank_(graph_theory)