Graph theory

Graph theory is a branch of mathematics that models discrete sets of objects with pairwise relations between them. The objects are called nodes or vertices. The relations are called links or edges. Customarily the nodes are drawn as circles and the links as lines between the circles to form the graph. A simple graph has no more than one link between two different nodes. A connected graph is one where there is a path of links between any two nodes. A planar graph is one where no link crosses over any other.

A map divided into discrete geographic units for redistricting can be translated into a graph. Each geographic unit is associated with a node. Contiguity defines links between nodes, and for a contiguous map without point contiguity the result is a simple connected planar graph. Some links may be eliminated if they are not defined as connections.

In redistricting each geographic unit is associated with population. Mathematically this is the same as having weighted nodes. The population of a graph or subgraph is the sum of the weights of its nodes. The redistricting problem of forming k districts is to partition the graph into k connected subgraphs such that each subgraph is consistent with population equality.