TOPICS
Search

Connected Graph


ConnectedGraph

A connected graph is graph that is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph. A graph that is not connected is said to be disconnected. This definition means that the null graph and singleton graph are considered connected, while empty graphs on n>=2 nodes are disconnected.

According to West (2001, p. 150), the singleton graph K_1, "is annoyingly inconsistent" since it is connected (specifically, 1-connected), but for consistency in discussing connectivity, it is considered to have vertex connectivity kappa(K_1)=0.

If A is the adjacency matrix of a simple graph G, then entry (i,j) of A^k is the number of k-walks from vertex i to vertex j. As a result, a graph on n>1 nodes is connected iff

 sum_(k=1)^(n-1)A^k

has no matrix element equal to zero.

A connected graph on n>1 nodes satisfies

 sum_(i=1)^nrho(v_i)>=1/2(n-1),

where rho(v_i) is the vertex degree of vertex i (and where the inequality can be made strict except in the case of the singleton graph K_1). However while this condition is necessary for a graph to be connected, it is not sufficient; an arbitrary graph satisfying the above inequality may be connected or disconnected.

The number of n-node connected unlabeled graphs for n=1, 2, ... are 1, 1, 2, 6, 21, 112, 853, 11117, 261080, ... (OEIS A001349). The total number of (not necessarily connected) unlabeled n-node graphs is given by the Euler transform of the preceding sequence, 1, 2, 4, 11, 34, 156, 1044, 12346, ... (OEIS A000088; Sloane and Plouffe 1995, p. 20). Furthermore, in general, if a_n is the number of unlabeled connected graphs on n nodes satisfying some property, then the Euler transform b_n is the total number of unlabeled graphs (connected or not) with the same property. This application of the Euler transform is called Riddell's formula.

The numbers of connected labeled graphs on n-nodes are 1, 1, 4, 38, 728, 26704, ... (OEIS A001187), and the total number of (not necessarily connected) labeled n-node graphs is given by the exponential transform of the preceding sequence: 1, 2, 8, 64, 1024, 32768, ... (OEIS A006125; Sloane and Plouffe 1995, p. 19).

An efficient enumeration of connected graphs on n nodes can be done using the program geng (part of nauty) by B. McKay using the syntax geng -c n. However, since the order in which graphs are returned by the geng program changes as a function of time as improvements are made, the canonical ordering given on McKay's website is used here and in GraphData.

A graph may be tested in the Wolfram Language to see if it is a connected graph using ConnectedGraphQ[g].

If G is disconnected, then its complement G^_ is connected (Skiena 1990, p. 171; Bollobás 1998). However, the converse is not true, as can be seen using the example of the cycle graph C_5 which is connected and isomorphic to its complement.

kConnectedGraph2kConnectedGraph3

One can also speak of k-connected graphs (i.e., graphs with vertex connectivity k) in which each vertex has degree at least k (i.e., the minimum of the degree sequence is >=k). 1-connected graphs are therefore connected with minimal degree >=1.


See also

Algebraic Connectivity, Biconnected Graph, Degree Sequence, Disconnected Graph, Edge Connectivity, Euler Transform, k-Connected Graph, Network, Planar Connected Graph, Polyhedral Graph, Polynema, Regular Graph, Riddell's Formula, Scale-Free Network, Sequential Graph, Steinitz's Theorem, Tait's Hamiltonian Graph Conjecture, Vertex Connectivity Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Bollobás, B. Modern Graph Theory. New York: Springer-Verlag, 1998.Cadogan, C. C. "The Möbius Function and Connected Graphs." J. Combin. Th. B 11, 193-200, 1971.Chartrand, G. "Connected Graphs." §2.3 in Introductory Graph Theory. New York: Dover, pp. 41-45, 1985.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 13, 1994.Harary, F. and Palmer, E. M. "Connected Graphs." §1.2 in Graphical Enumeration. New York: Academic Press, pp. 6-9, 1973.McKay, B. "Graphs." http://cs.anu.edu.au/~bdm/data/graphs.html.Skiena, S. "Connectivity." §5.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 171-180, 1990.Sloane, N. J. A. Sequences A000088/M1253, A001187/M3671, and A006125/M1897 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.Tutte, W. T. Connectivity in Graphs. Toronto, Canada: Toronto University Press, 1967.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

Referenced on Wolfram|Alpha

Connected Graph

Cite this as:

Weisstein, Eric W. "Connected Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ConnectedGraph.html

Subject classifications