## Linear Algebra and Its Applications, Exercise 2.5.18

Exercise 2.5.18. Consider a directed graph of $n$ nodes, where every node has a edge connecting it to every other node. How many edges are in this complete graph?

Answer: Each of the $n$ nodes has a connection to the $n-1$ other nodes. This would normally produce a total of $n(n-1)$ connections; however in order to avoid double counting a given edge we have to divide this value by 2. (In other words an edge from node $i$ to node $j$ counts as a connection for both nodes.) The total number of edges in the complete graph is therefore $n(n-1)/2$.

For example, a 2-node complete graph has $2 \cdot (2-1)/2 = 2/2 = 1$ edge, a 3-node complete graph has $3 \cdot (3-1)/2 = 6/2 = 3$ edges, a 4-node complete graph has $4 \cdot (4-1)/2 = 12/2 = 6$ edges, and so on.

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition , Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books .

This entry was posted in linear algebra. Bookmark the permalink.