Graph Theory and Network Structure: From Map Colouring to Social Connectivity

Social media followers, connective routes across a country, and electrical grids/electrical networks all have a commonality; they form relationships with solutions based in graph theory. Graph theory is the study of graphs and their properties, where a graph is defined as an ordered pair (V, E). V refers to the set of vertices (nodes) and E refers to the set of edges (links) which connect the vertices (Dehmer et al. 2017; Kothimbire et al. 2025). This field of network science has major relevance to important networks such as power grids (network of transmission lines and generators), or even family and friendship relationships (social network) (Barabási 2016). 

One of the most famous graph theory problems is the “four-colour problem,” which involves finding the minimum number of colours needed to fill in a map such that no adjacent regions have the same colour. The map is constrained by the following properties: 1) countries are bounded by simple closed curves and each country is connected, and 2) two countries are adjacent only if they share a border with part of a curve (Wilson 2002). Consider the example in Figure 1, which cannot be coloured using only three colours.

This problem raises the question of how many colours are needed to colour all maps considering these restrictions, with the claim being that it would never take more than four. Since the original 1852 conjecture, it took until the 1960s to show that larger cases of maps could be reduced, facilitating the work of inductive proofs (Wilson 2002). In summary, if a graph fails to satisfy 4 colours, then there is a local obstruction. Thus, every graph that is a ‘counter-example’ to the 4 colour theorem could be reduced to a finite set of configurations, which then could be proven reducible. Eventually by the year 1976, Kenneth Appel and Wolfgang Haken took over 1000 hours of computer run-code time to verify this argument, which is generally accepted by the field. However, to this day, there has not been a full “human-made” proof, as all arguments have required computer code (Wilson 2002). The unique solutions of the 4 colour problem can inspire other resolutions in graph theory.

Another engrossing  application is for the study of social relationships. Let us say we want to examine transitivity, and determine if two neighbors of a node have a high probability of also being neighbors (Kothimbire et al. 2025). This gives rise to “clustering coefficients,” which measures how closely two nodes are likely to cluster together (Figure 2). 

This application is fascinating because it can indicate and predict the probability of a network forming close relationships, such as the likelihood of mutual friends becoming direct friends. 

Altogether, the study of graph theory, the general ideas of connectivity and adjectivity can explain how a  network’s topology can influence behaviours within it (Kothimbire et al. 2025). This means that in larger, real-life applications, influential nodes or vulnerabilities in a system can be predicted. The ability to exhibit multi-dimensional relationships in multilayer networks have intriguing implications for generative models, algebraic topology, clinical and translational research, and more.

References

Barabási, Albert-László. 2016. Network Science. http://networksciencebook.com/.

Dehmer, Matthias, Frank Emmert-Streib, and Yongtang Shi. 2017. “Quantitative Graph Theory: A New Branch of Graph Theory and Network Science.” Information Sciences 418–419 (December): 575–80. https://doi.org/10.1016/j.ins.2017.08.009.

Kothimbire, Mrs D. K., D. S. Shelke, A. P. Yalpale, Mrs S. V. Gaikwad, and R. N. Shinde. 2025. “A Comprehensive Review of Graph Theory Applications in Network Analysis.” International Journal Of Mathematics And Computer Research 13 (3): 4956–67. https://doi.org/10.47191/ijmcr/v13i3.08.

Wilson, Robert A. 2002. Graphs, Colourings and the Four-Colour Theorem. OUP Oxford.