ConnectedGraphQ

ConnectedGraphQ[g]

yields True if the graph g is connected, and False otherwise.

Details

  • ConnectedGraphQ works for any graph object.
  • A graph is connected if there is a path between every pair of vertices.

Examples

open allclose all

Basic Examples  (2)

Test whether a graph is connected:

A graph with isolated vertices is not connected:

Scope  (6)

Test undirected graphs:

Directed graphs:

Multigraphs:

Mixed graphs:

ConnectedGraphQ gives False for anything that is not a connected graph:

ConnectedGraphQ works with large graphs:

Applications  (1)

Compute the probability that the Watts–Strogatz random graph model is connected:

Properties & Relations  (5)

The graph distance matrix of a connected graph does not have entries:

Connected graph:

Disconnected graph:

The minimum number of edges in a connected graph with vertices is :

A path graph with vertices has exactly edges:

The sum of the vertex degrees of a connected graph is greater than for the underlying simple graph:

A disconnected graph:

An undirected tree is connected:

An undirected path is connected:

Wolfram Research (2010), ConnectedGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/ConnectedGraphQ.html.

Text

Wolfram Research (2010), ConnectedGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/ConnectedGraphQ.html.

CMS

Wolfram Language. 2010. "ConnectedGraphQ." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/ConnectedGraphQ.html.

APA

Wolfram Language. (2010). ConnectedGraphQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/ConnectedGraphQ.html

BibTeX

@misc{reference.wolfram_2025_connectedgraphq, author="Wolfram Research", title="{ConnectedGraphQ}", year="2010", howpublished="\url{https://reference.wolfram.com/language/ref/ConnectedGraphQ.html}", note=[Accessed: 22-February-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_connectedgraphq, organization={Wolfram Research}, title={ConnectedGraphQ}, year={2010}, url={https://reference.wolfram.com/language/ref/ConnectedGraphQ.html}, note=[Accessed: 22-February-2025 ]}