2.8 Order and Size

As graphs are really just representations of the real world relationships that they are meant to describe, they can be as varied as those relationships. As such, language has developed to explain different facets of a graph.

The order of a graph is the number of nodes in the graph. More accurately, keeping in mind that the graph is really a set of a set of nodes and edges, the order is the cardinality of V(N). Cardinality is simply a mathematical term for how many components there are in a set. Thus, the graph in Figure 1.3 has an order of nine, while Figure 1.4 has an order of seven. Going forward, when you see the variable n, it represents the number of nodes in the graph.

Likewise, the cardinality of the set E(M) is the number of edges in the graph. The cardinality of the set E(M) in Figure 1.3 is 16, while in Figure 1.4 it is 11. If you say the cardinality of the graph in Figure 1.3 is 16, we can all understand that you are referring to the number of edges, as you would use the term order if you were talking about the number of nodes. Likewise, in future notion, the number of edges in the graph will be represented as variable m.

Finally, the size of the graph is defined as how many edges there could possibly be if everyone had a relationship with everyone else in the network. It is the maximum possible number of ties, and is calculated as [n(n-1)]/2 for an undirected network, and [n(n-1)] for a directed network.