Mathematical theory of networks. A graph consists of vertices (also called points or nodes) and edges (lines) connecting certain pairs of vertices. An edge that connects a node to itself is called a loop. In 1735 Leonhard Euler published an analysis of an old puzzle concerning the possibility of crossing every one of seven bridges (no bridge twice) that span a forked river flowing past an island. Euler's proof that no such path exists and his generalization of the problem to all possible networks are now recognized as the origin of both graph theory and topology. Since the mid-20th century, graph theory has become a standard tool for analyzing and designing communications networks, power transmission systems, transportation networks, and computer architectures.
Learn more about graph theory with a free trial on Britannica.com.
In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth ≥ 4 is triangle-free.