Connecting the brain
The human brain can be modeled as a
simple graph
, with each anatomical area represented as node. The lack of a clear, obvious choice of what should represent a node in a functional brain network has resulted in the analysis of brain networks across a wide range of scales, ranging from
70
-nodes to
140,000
-node whole brain networks.
Let us assume that in our model, the brain has exactly 70 nodes. What is the minimum number of connections (between distinct nodes) that are needed to guarantee that the graph is connected , no matter what the connections are?
Details and assumptions
- A simple graph, also called a strict graph, is an unweighted, undirected graph containing no graph loops or multiple edges.
- Connected means that there exists a path between every pair of nodes.
The answer is 2347.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Consider the worst-case where there are 69 nodes which forms a complete graph (this has (69 choose 2) nodes), then by following the rule of simple graph we can only connect the last node to any of the 69 nodes which ensures the graph is connected no matter what the connection is.
(69 choose 2) + 1 = 2347