Component (graph theory)

Last updated

A graph with three components Pseudoforest.svg
A graph with three components

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.

Contents

The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices. In random graphs, a frequently occurring phenomenon is the incidence of a giant component, one component that is significantly larger than the others; and of a percolation threshold, an edge probability above which a giant component exists and below which it does not.

The components of a graph can be constructed in linear time, and a special case of the problem, connected-component labeling, is a basic technique in image analysis. Dynamic connectivity algorithms maintain components as edges are inserted or deleted in a graph, in low time per change. In computational complexity theory, connected components have been used to study algorithms with limited space complexity, and sublinear time algorithms can accurately estimate the number of components.

Definitions and examples

A cluster graph with seven components Equivalentie.svg
A cluster graph with seven components

A component of a given undirected graph may be defined as a connected subgraph that is not part of any larger connected subgraph. For instance, the graph shown in the first illustration has three components. Every vertex of a graph belongs to one of the graph's components, which may be found as the induced subgraph of the set of vertices reachable from . [1] Every graph is the disjoint union of its components. [2] Additional examples include the following special cases:

Another definition of components involves the equivalence classes of an equivalence relation defined on the graph's vertices. In an undirected graph, a vertex is reachable from a vertex if there is a path from to , or equivalently a walk (a path allowing repeated vertices and edges). Reachability is an equivalence relation, since:

The equivalence classes of this relation partition the vertices of the graph into disjoint sets, subsets of vertices that are all reachable from each other, with no additional reachable pairs outside of any of these subsets. Each vertex belongs to exactly one equivalence class. The components are then the induced subgraphs formed by each of these equivalence classes. [7] Alternatively, some sources define components as the sets of vertices rather than as the subgraphs they induce. [8]

Similar definitions involving equivalence classes have been used to defined components for other forms of graph connectivity, including the weak components [9] and strongly connected components of directed graphs [10] and the biconnected components of undirected graphs. [11]

Number of components

The number of components of a given finite graph can be used to count the number of edges in its spanning forests: In a graph with vertices and components, every spanning forest will have exactly edges. This number is the matroid-theoretic rank of the graph, and the rank of its graphic matroid. The rank of the dual cographic matroid equals the circuit rank of the graph, the minimum number of edges that must be removed from the graph to break all its cycles. In a graph with edges, vertices and components, the circuit rank is . [12]

A graph can be interpreted as a topological space in multiple ways, for instance by placing its vertices as points in general position in three-dimensional Euclidean space and representing its edges as line segments between those points. [13] The components of a graph can be generalized through these interpretations as the topological connected components of the corresponding space; these are equivalence classes of points that cannot be separated by pairs of disjoint closed sets. Just as the number of connected components of a topological space is an important topological invariant, the zeroth Betti number, the number of components of a graph is an important graph invariant, and in topological graph theory it can be interpreted as the zeroth Betti number of the graph. [3]

The number of components arises in other ways in graph theory as well. In algebraic graph theory it equals the multiplicity of 0 as an eigenvalue of the Laplacian matrix of a finite graph. [14] It is also the index of the first nonzero coefficient of the chromatic polynomial of the graph, and the chromatic polynomial of the whole graph can be obtained as the product of the polynomials of its components. [15] Numbers of components play a key role in the Tutte theorem characterizing finite graphs that have perfect matchings [16] and the associated Tutte–Berge formula for the size of a maximum matching, [17] and in the definition of graph toughness. [18]

Algorithms

It is straightforward to compute the components of a finite graph in linear time (in terms of the numbers of the vertices and edges of the graph) using either breadth-first search or depth-first search. In either case, a search that begins at some particular vertex will find the entire component containing (and no more) before returning. All components of a graph can be found by looping through its vertices, starting a new breadth-first or depth-first search whenever the loop reaches a vertex that has not already been included in a previously found component. Hopcroft & Tarjan (1973) describe essentially this algorithm, and state that it was already "well known". [19]

Connected-component labeling, a basic technique in computer image analysis, involves the construction of a graph from the image and component analysis on the graph. The vertices are the subset of the pixels of the image, chosen as being of interest or as likely to be part of depicted objects. Edges connect adjacent pixels, with adjacency defined either orthogonally according to the Von Neumann neighborhood, or both orthogonally and diagonally according to the Moore neighborhood. Identifying the connected components of this graph allows additional processing to find more structure in those parts of the image or identify what kind of object is depicted. Researchers have developed component-finding algorithms specialized for this type of graph, allowing it to be processed in pixel order rather than in the more scattered order that would be generated by breadth-first or depth-first searching. This can be useful in situations where sequential access to the pixels is more efficient than random access, either because the image is represented in a hierarchical way that does not permit fast random access or because sequential access produces better memory access patterns. [20]

There are also efficient algorithms to dynamically track the components of a graph as vertices and edges are added, by using a disjoint-set data structure to keep track of the partition of the vertices into equivalence classes, replacing any two classes by their union when an edge connecting them is added. These algorithms take amortized time per operation, where adding vertices and edges and determining the component in which a vertex falls are both operations, and is a very slowly growing inverse of the very quickly growing Ackermann function. [21] One application of this sort of incremental connectivity algorithm is in Kruskal's algorithm for minimum spanning trees, which adds edges to a graph in sorted order by length and includes an edge in the minimum spanning tree only when it connects two different components of the previously-added subgraph. [22] When both edge insertions and edge deletions are allowed, dynamic connectivity algorithms can still maintain the same information, in amortized time per change and time per connectivity query, [23] or in near-logarithmic randomized expected time. [24]

Components of graphs have been used in computational complexity theory to study the power of Turing machines that have a working memory limited to a logarithmic number of bits, with the much larger input accessible only through read access rather than being modifiable. The problems that can be solved by machines limited in this way define the complexity class L. It was unclear for many years whether connected components could be found in this model, when formalized as a decision problem of testing whether two vertices belong to the same component, and in 1982 a related complexity class, SL, was defined to include this connectivity problem and any other problem equivalent to it under logarithmic-space reductions. [25] It was finally proven in 2008 that this connectivity problem can be solved in logarithmic space, and therefore that SL = L. [26]

In a graph represented as an adjacency list, with random access to its vertices, it is possible to estimate the number of connected components, with constant probability of obtaining additive (absolute) error at most , in sublinear time . [27]

In random graphs

An Erdos-Renyi-Gilbert random graph with 1000 vertices with edge probability
p
=
1
/
(
n
-
1
)
{\displaystyle p=1/(n-1)}
(in the critical range), showing a large component and many small ones Critical 1000-vertex Erdos-Renyi-Gilbert graph.svg
An Erdős–Rényi–Gilbert random graph with 1000 vertices with edge probability (in the critical range), showing a large component and many small ones

In random graphs the sizes of components are given by a random variable, which, in turn, depends on the specific model of how random graphs are chosen. In the version of the Erdős–Rényi–Gilbert model, a graph on vertices is generated by choosing randomly and independently for each pair of vertices whether to include an edge connecting that pair, with probability of including an edge and probability of leaving those two vertices without an edge connecting them. [28] The connectivity of this model depends on , and there are three different ranges of with very different behavior from each other. In the analysis below, all outcomes occur with high probability, meaning that the probability of the outcome is arbitrarily close to one for sufficiently large values of . The analysis depends on a parameter , a positive constant independent of that can be arbitrarily close to zero.

Subcritical
In this range of , all components are simple and very small. The largest component has logarithmic size. The graph is a pseudoforest. Most of its components are trees: the number of vertices in components that have cycles grows more slowly than any unbounded function of the number of vertices. Every tree of fixed size occurs linearly many times. [29]
Critical
The largest connected component has a number of vertices proportional to . There may exist several other large components; however, the total number of vertices in non-tree components is again proportional to . [30]
Supercritical
There is a single giant component containing a linear number of vertices. For large values of its size approaches the whole graph: where is the positive solution to the equation . The remaining components are small, with logarithmic size. [31]

In the same model of random graphs, there will exist multiple connected components with high probability for values of below a significantly higher threshold, , and a single connected component for values above the threshold, . This phenomenon is closely related to the coupon collector's problem: in order to be connected, a random graph needs enough edges for each vertex to be incident to at least one edge. More precisely, if random edges are added one by one to a graph, then with high probability the first edge whose addition connects the whole graph touches the last isolated vertex. [32]

For different models including the random subgraphs of grid graphs, the connected components are described by percolation theory. A key question in this theory is the existence of a percolation threshold, a critical probability above which a giant component (or infinite component) exists and below which it does not. [33]

Related Research Articles

<span class="mw-page-title-main">Eulerian path</span> Trail in a graph that visits each edge once

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

<span class="mw-page-title-main">Spanning tree</span> Tree which includes all vertices of a graph

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

<span class="mw-page-title-main">Strongly connected component</span> Partition of a graph whose components are reachable from all vertices

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of a directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E )).

<span class="mw-page-title-main">Loop-erased random walk</span> Model for a random simple path

In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics, physics and quantum field theory. It is intimately connected to the uniform spanning tree, a model for a random tree. See also random walk for more general treatment of this topic.

In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON, which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same connected component. This problem is also called the undirected reachability problem. It does not matter whether many-one reducibility or Turing reducibility is used. Although originally described in terms of symmetric Turing machines, that equivalent formulation is very complex, and the reducibility definition is what is used in practice.

<span class="mw-page-title-main">Bridge (graph theory)</span> Edge in node-link graph whose removal would disconnect the graph

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

<span class="mw-page-title-main">Connectivity (graph theory)</span> Basic concept of graph theory

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

<span class="mw-page-title-main">Hadwiger conjecture (graph theory)</span> Unproven generalization of the four-color theorem

In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

<span class="mw-page-title-main">Maximal independent set</span> Independent set which is not a subset of any other independent set

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.

<span class="mw-page-title-main">Feedback arc set</span> Edges that hit all cycles in a graph

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

<span class="mw-page-title-main">Giant component</span> Large connected component of a random graph

In network theory, a giant component is a connected component of a given random graph that contains a significant fraction of the entire graph's vertices.

<span class="mw-page-title-main">Biconnected component</span> Maximal biconnected subgraph

In graph theory, a biconnected component is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components.

In graph theory, a graph is said to be a pseudorandom graph if it obeys certain properties that random graphs obey with high probability. There is no concrete definition of graph pseudorandomness, but there are many reasonable characterizations of pseudorandomness one can consider.

<span class="mw-page-title-main">Rado graph</span> Infinite graph containing all countable graphs

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann. The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

<span class="mw-page-title-main">Erdős–Rényi model</span> Two closely related models for generating random graphs

In the mathematical field of graph theory, the Erdős–Rényi model refers to one of two closely related models for generating random graphs or the evolution of a random network. These models are named after Hungarian mathematicians Paul Erdős and Alfréd Rényi, who introduced one of the models in 1959. Edgar Gilbert introduced the other model contemporaneously with and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely. In the model introduced by Gilbert, also called the Erdős–Rényi–Gilbert model, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

<span class="mw-page-title-main">Random geometric graph</span> In graph theory, the mathematically simplest spatial network

In graph theory, a random geometric graph (RGG) is the mathematically simplest spatial network, namely an undirected graph constructed by randomly placing N nodes in some metric space and connecting two nodes by a link if and only if their distance is in a given range, e.g. smaller than a certain neighborhood radius, r.

<span class="mw-page-title-main">Pseudoforest</span> Graph with at most one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

Property testing is a field of theoretical computer science, concerned with the design of super-fast algorithms for approximate decision making, where the decision refers to properties or parameters of huge objects.

In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture is a group of related conjectures about the number of questions of the form "Is there an edge between vertex and vertex ?" that have to be answered to determine whether or not an undirected graph has a particular property such as planarity or bipartiteness. They are named after Stål Aanderaa, Richard M. Karp, and Arnold L. Rosenberg. According to the conjecture, for a wide class of properties, no algorithm can guarantee that it will be able to skip any questions: any algorithm for determining whether the graph has the property, no matter how clever, might need to examine every pair of vertices before it can give its answer. A property satisfying this conjecture is called evasive.

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal, who first posed it as an open problem in a paper from 1977.

References

  1. Clark, John; Holton, Derek Allan (1995), A First Look at Graph Theory, Allied Publishers, p. 28, ISBN   9788170234630, archived from the original on 2022-01-08, retrieved 2022-01-07
  2. Joyner, David; Nguyen, Minh Van; Phillips, David (May 10, 2013), "1.6.1 Union, intersection, and join", Algorithmic Graph Theory and Sage (0.8-r1991 ed.), Google, pp. 34–35, archived from the original on January 16, 2016, retrieved January 8, 2022
  3. 1 2 Tutte, W. T. (1984), Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 21, Reading, Massachusetts: Addison-Wesley, p. 15, ISBN   0-201-13520-5, MR   0746795, archived from the original on 2022-01-07, retrieved 2022-01-07
  4. 1 2 Thulasiraman, K.; Swamy, M. N. S. (2011), Graphs: Theory and Algorithms, John Wiley & Sons, p. 9, ISBN   978-1-118-03025-7, archived from the original on 2022-01-07, retrieved 2022-01-07
  5. Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, New York: Springer-Verlag, p. 6, doi:10.1007/978-1-4612-0619-4, ISBN   0-387-98488-7, MR   1633290, archived from the original on 2022-01-08, retrieved 2022-01-08
  6. McColl, W. F.; Noshita, K. (1986), "On the number of edges in the transitive closure of a graph", Discrete Applied Mathematics , 15 (1): 67–73, doi:10.1016/0166-218X(86)90020-X, MR   0856101
  7. Foldes, Stephan (2011), Fundamental Structures of Algebra and Discrete Mathematics, John Wiley & Sons, p. 199, ISBN   978-1-118-03143-8, archived from the original on 2022-01-07, retrieved 2022-01-07
  8. Siek, Jeremy; Lee, Lie-Quan; Lumsdaine, Andrew (2001), "7.1 Connected components: Definitions", The Boost Graph Library: User Guide and Reference Manual, Addison-Wesley, pp. 97–98
  9. Knuth, Donald E. (January 15, 2022), "Weak components", The Art of Computer Programming, Volume 4, Pre-Fascicle 12A: Components and Traversal (PDF), pp. 11–14, archived (PDF) from the original on January 18, 2022, retrieved March 1, 2022
  10. Lewis, Harry; Zax, Rachel (2019), Essential Discrete Mathematics for Computer Science, Princeton University Press, p. 145, ISBN   978-0-691-19061-7, archived from the original on 2022-01-08, retrieved 2022-01-08
  11. Kozen, Dexter C. (1992), "4.1 Biconnected components", The Design and Analysis of Algorithms, Texts and Monographs in Computer Science, New York: Springer-Verlag, pp. 20–22, doi:10.1007/978-1-4612-4400-4, ISBN   0-387-97687-6, MR   1139767, S2CID   27747202, archived from the original on 2022-01-08, retrieved 2022-01-08
  12. Wilson, R. J. (1973), "An introduction to matroid theory", The American Mathematical Monthly , 80 (5): 500–525, doi:10.1080/00029890.1973.11993318, JSTOR   2319608, MR   0371694
  13. Wood, David R. (2014), "Three-dimensional graph drawing", in Kao, Ming-Yang (ed.), Encyclopedia of Algorithms (PDF), Springer, pp. 1–7, doi:10.1007/978-3-642-27848-8_656-1, ISBN   978-3-642-27848-8, archived (PDF) from the original on 2022-01-08, retrieved 2022-01-08
  14. Cioabă, Sebastian M. (2011), "Some applications of eigenvalues of graphs", in Dehmer, Matthias (ed.), Structural Analysis of Complex Networks, New York: Birkhäuser/Springer, pp. 357–379, doi:10.1007/978-0-8176-4789-6_14, ISBN   978-0-8176-4788-9, MR   2777924 ; see proof of Lemma 5, p. 361 Archived 2022-01-08 at the Wayback Machine
  15. Read, Ronald C. (1968), "An introduction to chromatic polynomials", Journal of Combinatorial Theory , 4: 52–71, doi: 10.1016/S0021-9800(68)80087-0 , MR   0224505 ; see Theorem 2, p. 59, and corollary, p. 65
  16. Tutte, W. T. (1947), "The factorization of linear graphs", The Journal of the London Mathematical Society , 22 (2): 107–111, doi:10.1112/jlms/s1-22.2.107, MR   0023048
  17. Berge, Claude (1958), "Sur le couplage maximum d'un graphe", Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences , 247: 258–259, MR   0100850
  18. Chvátal, Václav (1973), "Tough graphs and Hamiltonian circuits", Discrete Mathematics , 5 (3): 215–228, doi: 10.1016/0012-365X(73)90138-6 , MR   0316301
  19. Hopcroft, John; Tarjan, Robert (June 1973), "Algorithm 447: efficient algorithms for graph manipulation", Communications of the ACM , 16 (6): 372–378, doi: 10.1145/362248.362272 , S2CID   14772567
  20. Dillencourt, Michael B.; Samet, Hanan; Tamminen, Markku (1992), "A general approach to connected-component labeling for arbitrary image representations", Journal of the ACM , 39 (2): 253–280, CiteSeerX   10.1.1.73.8846 , doi:10.1145/128749.128750, MR   1160258, S2CID   1869184
  21. Bengelloun, Safwan Abdelmajid (December 1982), Aspects of Incremental Computing (PhD thesis), Yale University, p. 12, ProQuest   303248045
  22. Skiena, Steven (2008), "6.1.2 Kruskal's Algorithm", The Algorithm Design Manual, Springer, pp. 196–198, Bibcode:2008adm..book.....S, doi:10.1007/978-1-84800-070-4, ISBN   978-1-84800-069-8, archived from the original on 2022-01-07, retrieved 2022-01-07
  23. Wulff-Nilsen, Christian (2013), "Faster deterministic fully-dynamic graph connectivity", in Khanna, Sanjeev (ed.), Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pp. 1757–1769, arXiv: 1209.5608 , doi:10.1137/1.9781611973105.126, ISBN   978-1-61197-251-1, S2CID   13397958
  24. Huang, Shang-En; Huang, Dawei; Kopelowitz, Tsvi; Pettie, Seth (2017), "Fully dynamic connectivity in amortized expected time", in Klein, Philip N. (ed.), Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 510–520, arXiv: 1609.05867 , doi:10.1137/1.9781611974782.32, S2CID   15585534
  25. Lewis, Harry R.; Papadimitriou, Christos H. (1982), "Symmetric space-bounded computation", Theoretical Computer Science , 19 (2): 161–187, doi: 10.1016/0304-3975(82)90058-5 , MR   0666539
  26. Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM , 55 (4): A17:1–A17:24, doi:10.1145/1391289.1391291, MR   2445014, S2CID   207168478
  27. Berenbrink, Petra; Krayenhoff, Bruce; Mallmann-Trenn, Frederik (2014), "Estimating the number of connected components in sublinear time", Information Processing Letters , 114 (11): 639–642, doi:10.1016/j.ipl.2014.05.008, MR   3230913
  28. Frieze, Alan; Karoński, Michał (2016), "1.1 Models and relationships", Introduction to Random Graphs, Cambridge University Press, Cambridge, pp. 3–9, doi:10.1017/CBO9781316339831, ISBN   978-1-107-11850-8, MR   3675279
  29. Frieze & Karoński (2016), 2.1 Sub-critical phase, pp. 20–33; see especially Theorem 2.8, p. 26, Theorem 2.9, p. 28, and Lemma 2.11, p. 29
  30. Frieze & Karoński (2016), 2.3 Phase transition, pp. 39–45
  31. Frieze & Karoński (2016), 2.2 Super-critical phase, pp. 33; see especially Theorem 2.14, p. 33–39
  32. Frieze & Karoński (2016), 4.1 Connectivity, pp. 64–68
  33. Cohen, Reuven; Havlin, Shlomo (2010), "10.1 Percolation on complex networks: Introduction", Complex Networks: Structure, Robustness and Function, Cambridge University Press, pp. 97–98, ISBN   978-1-139-48927-0, archived from the original on 2022-01-10, retrieved 2022-01-10