Editing Fundamental group (section)

=== Graphs ===

The fundamental group can be defined for discrete structures too. In particular, consider a [[Connectivity (graph theory)|connected]] [[graph (discrete mathematics)|graph]] {{nowrap|''G'' {{=}} (''V'', ''E'')}}, with a designated vertex ''v''<sub>0</sub> in ''V''. The loops in ''G'' are the [[cycle (graph theory)|cycles]] that start and end at ''v''<sub>0</sub>.<ref>{{Cite web|title=Meaning of Fundamental group of a graph|url=https://math.stackexchange.com/questions/515896/meaning-of-fundamental-group-of-a-graph|access-date=2020-07-28|website=Mathematics Stack Exchange}}</ref> Let ''T'' be a [[spanning tree]] of ''G''. Every simple loop in ''G'' contains exactly one edge in ''E'' \ ''T''; every loop in ''G'' is a concatenation of such simple loops. Therefore, the fundamental group of a [[graph (discrete mathematics)|graph]] is a [[free group]], in which the number of generators is exactly the number of edges in ''E'' \ ''T''. This number equals {{nowrap|{{!}}''E''{{!}} − {{!}}''V''{{!}} + 1}}.<ref>{{Cite web|last=Simon|first=J|date=2008|title=Example of calculating the fundamental group of a graph G|url=http://homepage.divms.uiowa.edu/~jsimon/COURSES/M201Fall08/HandoutsAndHomework/Graph1.pdf|archive-url=https://web.archive.org/web/20200728164140/http://homepage.divms.uiowa.edu/~jsimon/COURSES/M201Fall08/HandoutsAndHomework/Graph1.pdf|archive-date=2020-07-28|url-status=dead|access-date=2020-07-28}}</ref>

For example, suppose ''G'' has 16 vertices arranged in 4 rows of 4 vertices each, with edges connecting vertices that are adjacent horizontally or vertically. Then ''G'' has 24 edges overall, and the number of edges in each spanning tree is {{nowrap|16 − 1 {{=}} 15}}, so the fundamental group of ''G'' is the free group with 9 generators.<ref>{{Cite web|title=The Fundamental Groups of Connected Graphs - Mathonline|url=http://mathonline.wikidot.com/the-fundamental-groups-of-connected-graphs|access-date=2020-07-28|website=mathonline.wikidot.com}}</ref> Note that ''G'' has 9 "holes", similarly to a bouquet of 9 circles, which has the same fundamental group.