On Graph Theory (2000-2009)

"At the other end of the spectrum is, for example, graph theory, where the basic object, a graph, can be immediately comprehended. One will not get anywhere in graph theory by sitting in an armchair and trying to understand graphs better. Neither is it particularly necessary to read much of the literature before tackling a problem: it is of course helpful to be aware of some of the most important techniques, but the interesting problems tend to be open precisely because the established techniques cannot easily be applied." (Timothy Gowers, "The two cultures of mathematics", 2000)

"Euler's proof that in Königsberg there is no path crossing all seven bridges only once was based on a simple observation. Nodes with an odd number of links must be either the starting or the end point of the journey. A continuous path that goes through all the bridges can have only one starting and one end point. Thus, such a path cannot exist on a graph that has more than two nodes with an odd number of links. As the Königsberg graph had four such nodes, one could not find the desired path." (Albert-László Barabási, "Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life", 2002)

"Regular graphs are unique in that each node has exactly the same number of links. […] Such regularity is clearly absent from random graphs. The premise of the random network model is deeply egalitarian: We place the links completely randomly; thus all nodes have the same chance of getting one […] If the network is large, despite the links' completely random placement, almost all nodes will have approximately the same number of links." (Albert-László Barabási, "Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life", 2002) 

"There is an old debate', Erdos liked to say, 'about whether you create mathematics or just discover it. In other words, are the truths already there, even if we don't yet know them?' Erdos had a clear answer to this question: Mathematical truths are there among the list of absolute truths, and we just rediscover them. Random graph theory, so elegant and simple, seemed to him to belong to the eternal truths. Yet today we know that random networks played little role in assembling our universe. Instead, nature resorted to a few fundamental laws [...]. Erdos himself created mathematical truths and an alternative view of our world by developing random graph theory." (Albert-László Barabási, "Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life", 2002)

"In modern terminology, a collection of points in space (called vertices) and lines (called edges) joining selected pairs of those points is called a graph, and the study of graphs is called graph theory. A graph that can be drawn on the plane so that the joining lines intersect only at vertices is called a planar graph." (David Gay, "Explorations in Topology", 2007)

"The important graphs are the ones where some things are not connected to some other things. When the unenlightened ones try to be profound, they draw endless verbal comparisons between this topic, and that topic, which is like this, which is like that; until their graph is fully connected and also totally useless." (Eliezer S Yudkowsky,  "Mysterious Answers to Mysterious Questions", 2007)

"A first step in understanding complex systems is trying to understand patterns and regularities of interactions in a way which might make it possible to break the systems down into possible subcomponents. To do so, it is necessary to find a way of representing complex systems. […] A convenient way to represent complex systems is through graphs or networks." (Jörg Reichardt, "Structure in Complex Networks", 2009)

"A graph in mathematics is a set of nodes and a set of edges between pairs of those nodes; the edges are ordered or nonordered pairs, or a relation, that defines the pairs of nodes for which the relation being examined is valid. […] The edges can either be undirected or directed; directed edges depict a relation that requires the nodes to be ordered while an undirected edge defines a relation in which no ordering of the edges is implied." (Dennis M Buede, "The Engineering Design of Systems: Models and methods", 2009)

"A graph enables us to visualize a relation over a set, which makes the characteristics of relations such as transitivity and symmetry easier to understand. […] Notions such as paths and cycles are key to understanding the more complex and powerful concepts of graph theory. There are many degrees of connectedness that apply to a graph; understanding these types of connectedness enables the engineer to understand the basic properties that can be defined for the graph representing some aspect of his or her system. The concepts of adjacency and reachability are the first steps to understanding the ability of an allocated architecture of a system to execute properly." (Dennis M Buede, "The Engineering Design of Systems: Models and methods", 2009)

"For the study of the topology of the interactions of a complex system it is of central importance to have proper random null models of networks, i.e., models of how a graph arises from a random process. Such models are needed for comparison with real world data. When analyzing the structure of real world networks, the null hypothesis shall always be that the link structure is due to chance alone. This null hypothesis may only be rejected if the link structure found differs significantly from an expectation value obtained from a random model. Any deviation from the random null model must be explained by non-random processes." (Jörg Reichardt, "Structure in Complex Networks", 2009)