On Graph Theory (2010-)

"A conceptual model is a qualitative description of 'some aspect of the behaviour of a natural system'. This description is usually verbal, but may also be accompanied by figures and graphs." (Howard S. Wheater et al., "Groundwater Modelling in Arid and Semi-Arid Areas", 2010) 

"First, what are the 'graphs' studied in graph theory? They are not graphs of functions as studied in calculus and analytic geometry. They are (usually finite) structures consisting of vertices and edges. As in geometry, we can think of vertices as points (but they are denoted by thick dots in diagrams) and of edges as arcs connecting pairs of distinct vertices. The positions of the vertices and the shapes of the edges are irrelevant: the graph is completely specified by saying which vertices are connected by edges. A common convention is that at most one edge connects a given pair of vertices, so a graph is essentially just a pair of sets: a set of objects." (John Stillwell, "Mathematics and Its History", 2010)

"Infinite reasoning is likewise essential for graph theory. The field had its origins in topology, and it is still relevant there, but it has expanded extraordinarily far in other directions. Graph theory today is exploring the boundaries of finite provability first exposed by Gödel’s incompleteness theorem." (John Stillwell, "Mathematics and Its History", 2010)

"Social network analysis has been important for the further development of graph theory, for example with respect to introducing metrics for identifying importance of people or groups. For example, a person having many connections to other people may be considered relatively important. Likewise, a person at the center of a network would seem to be more influential than someone at the edge. What graph theory provides us are the tools to formally describe what we mean by relatively important, or having more influence. Moreover, using graph theory we can easily come up with alternatives for describing importance and such. Having such tools has also facilitated being more precise in statements regarding the position or role that person has within a community." (Maarten van Steen, "Graph Theory and Complex Networks: An Introduction", 2010) 

"The difference between necessary and sufficient conditions seems an obvious one, yet they are surprisingly often confused in mathematical proofs. Formally, in graph theory, conditions are used to prove properties of graphs. When a condition C is said to be necessary, this means that a property P can hold only if C is met. When a condition C is said to be sufficient, this means that if C is met, then property P will hold true. And indeed, when property P is true if and only if condition C is met, indicates that C is a necessary and sufficient condition for property P to be valid." (Maarten van Steen, "Graph Theory and Complex Networks: An Introduction", 2010)

"The most naive branch of combinatorics is graph theory, a subject that is visual and easily grasped, yet rich in connections with other parts of mathematics." (John Stillwell, "Mathematics and Its History", 2010)

"Venn diagramming, it turns out, is a very effective technique for performing syllogistic reasoning. Its chief advantage (over the Euler graph in particular as we noted earlier) is the ability to incrementally add knowledge to the diagram. While an Euler graph has visual power in terms of representing the relations between sets very intuitively, it is impossible to combine more than one piece of information onto a Euler graph. A Venn diagram, on the other hand, easily lends itself to the representation of partial knowledge and can be manipulated to add successively more knowledge to the diagram. This means that when our knowledge of the relations between sets increases, we simply put in more symbols and shadings into the appropriate compartments of the Venn diagram. Thus we are able to accumulate knowledge in a Venn diagram. This capability turns out to be a powerful feature, one that endows Venn diagrams with a more dynamic quality that is sorely lacking in the Euler system." (Robbie T Nakatsu, "Diagrammatic Reasoning in AI", 2010)

"Graphs are among the most important abstract data structures in computer science, and the algorithms that operate on them are critical to modern life. Graphs have been shown to be powerful tools for modeling complex problems because of their simplicity and generality." (Jeremy Kepner & John Gilbert [Eds],"Graph Algorithms in the Language of Linear Algebra", 2011)

"Discrete Mathematics is a branch of mathematics dealing with finite or countable processes and elements. Graph Theory is an area in Discrete Mathematics which studies configurations involving a set of vertices interconnected by edges (called graphs). From humble beginnings and almost recreational type problems, Graph Theory has found its calling in the modern world of complex systems and especially of the computer. Graph Theory and its applications can be found not only in other branches of mathematics, but also in scientific disciplines such as engineering, computer science, operational research, management sciences and the life sciences." (Khee Meng Koh et al, " Graph theory: Undergraduate mathematics", 2015)

"The mathematical structure known as a graph has the valuable feature of helping us to visualize, to analyze, to generalize a situation or problem we may encounter and, in many cases, assisting us to understand it better and possibly find a solution." (Arthur Benjamin, "The fascinating world of graph theory", 2015)

"The theory of graphs is the fundamental study of relations in their purest, non-trivial form: binary connections between abstract points. And as so often in combinatorics, this simple assemblage of trivial objects results in a dazzlingly rich theory of seemingly endless depths." (Felix Reidl, "Structural Sparseness and Complex Networks", 2015) 

"Several areas of graph theory are concerned with the likelihood or certainty of the presence in a graph of various subgraphs or, more generally, of graph properties that emerge as the number of vertices and/or the number of edges increases. Collectively they are grouped as analytic graph theory." (Jonathan L Gross et al, "Topics in Graph Theory", 2023)

"Some connected graphs are 'more connected' than others. That is, a connected graph’s vulnerability to disconnection by edge- or vertex-deletion varies. Two numerical parameters, vertex-connectivity and edge-connectivity, are useful in measuring a graph’s connectedness. Intuitively, a network’s vulnerability should be closely related also to the number of  alternative paths between each pair of nodes. There is a rich body of mathematical results concerning this relationship, many of which are variations of a classical result of Menger, and some of these extend well beyond graph theory." (Jonathan L Gross et al, "Topics in Graph Theory", 2023)

"Spanning trees capture the connectedness of a graph in the most efficient way, and they provide a foundation for a systematic analysis of the cycle structure of a graph. Mathematicians regard the algebraic structures underlying the collection of cycles and edge-cuts of agraph as beautiful in their own right. Establishing connections between linear algebra and graph theory provides some powerful analytical tools for understanding a graph’s structure." (Jonathan L Gross et al, "Topics in Graph Theory", 2023)

"The relationship of planarity to topological graph theory is something like the relationship of plane geometry to what geometers call geometry, where mathematicians long ago began to develop concepts and methods to progress far beyond the plane. Whereas planarity consists mostly of relatively accessible ideas that were well understood several decades ago, topological graph theorists use newer methods to progress to all the other surfaces." (Jonathan L Gross et al, "Topics in Graph Theory", 2023)