Family Planning with Graph Theory

People often find graph theory too abstract to be applicable to their own lives. This post will try to change that.

A graph is a collection of vertices and edges. You might consider a Connect the Dots puzzle a graph, or a polygon, or a collection of cities on a road map, or a collection of nodes in a computer network--anything, really, that can be represented as a set of points between which meaningful connections can be made.

One quantitive property of graphs is density. The density of a graph tells you how close you are to the maximum possible number of edges. A completed Connect the Dots puzzle is an example a "sparse graph" (low density), but if you draw lines from every dot to every other dot, the graph will reach maximum density.

The maximum number of edges a graph can have is determined by the formula V*(V-1)/2, where V is the number of vertices. This can be easily verified using combinatorics, because it's the number of unique combinations of two chosen from a set of V elements: (V!) / (2! * (V-2)!).

It should be clear that the maximum number of edges grows exponentially with each additional vertex. If maximum density is to be maintained, for each new vertex added to a graph, edges must be added connecting the new vertex to all pre-existing vertices. Following is a visual example.



By this time, you may be wondering how any of this might relate to your own life and family planning. I'll explain by considering the number of possible fights that may occur among one's offspring.

If you have only one child, there are zero possible fights between this child and the other children, because there are no other children with which to fight.

If you have two children, there's obviously only one possible fight: the fight between Child A and Child B.

In the case of three children, there are three different possible fights: (A,B), (A,C) and (B,C).

Moving on to four children, the number of possible fights doubles: (A,B), (A,C), (A,D), (B,C), (B,D) and (C,D).

The number of fights possible with five children is interesting, but only theoretically so. In practical terms, it doesn't matter, because even four are perfectly capable of fighting all the time.

:)