WOLFRAM

Wolfram Language & System Documentation Center

ConnectedGraphQ[g]

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

Details
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Applications  
Properties & Relations  
See Also
Related Guides
Related Links
History
Cite this Page

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 all close all

Basic Examples  (2)

Test whether a graph is connected:

Wolfram Language code: Graph[{12, 23, 31}]
Wolfram Language code: ConnectedGraphQ[%]

A graph with isolated vertices is not connected:

Wolfram Language code: Graph[{1, 2, 3, 4}, {12, 23, 31}]
Wolfram Language code: ConnectedGraphQ[%]

Scope  (6)

Test undirected graphs:

Wolfram Language code: ConnectedGraphQ[[image]]

Directed graphs:

Wolfram Language code: ConnectedGraphQ[[image]]

Multigraphs:

Wolfram Language code: ConnectedGraphQ[[image]]

Mixed graphs:

Wolfram Language code: ConnectedGraphQ[[image]]

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

Wolfram Language code: ConnectedGraphQ[x]

ConnectedGraphQ works with large graphs:

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: Timing[ConnectedGraphQ[g]]

Applications  (1)

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

Wolfram Language code: 𝒢 = WattsStrogatzGraphDistribution[20, 0.5, 1];
Wolfram Language code: 𝒟 = GraphPropertyDistribution[Boole[ConnectedGraphQ[g]], g𝒢];
Wolfram Language code: NProbability[x == 1, x𝒟]

Properties & Relations  (5)

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

Wolfram Language code: g = CycleGraph[3]

Connected graph:

Wolfram Language code: GraphDistanceMatrix[g]//MatrixForm

Disconnected graph:

Wolfram Language code: g = Graph[{12, 34}]
Wolfram Language code: GraphDistanceMatrix[g]//MatrixForm

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

Wolfram Language code: PetersenGraph[5, 2]
Wolfram Language code: {ConnectedGraphQ[%], EdgeCount[%] ≥ VertexCount[%] - 1}

A path graph with vertices has exactly edges:

Wolfram Language code: PathGraph[Range[10]]
Wolfram Language code: {ConnectedGraphQ[%], EdgeCount[%] ≥ VertexCount[%] - 1}

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

Wolfram Language code: g = WheelGraph[4]
Wolfram Language code: {ConnectedGraphQ[g], Total[VertexDegree[g]] ≥ (VertexCount[g] - 1) / 2}

A disconnected graph:

Wolfram Language code: g = Graph[Range[10], {12}]
Wolfram Language code: {ConnectedGraphQ[g], Total[VertexDegree[g]] ≥ (VertexCount[g] - 1) / 2}

An undirected tree is connected:

Wolfram Language code: TreeGraph[{12, 13, 14}]
Wolfram Language code: {TreeGraphQ[%], ConnectedGraphQ[%]}

An undirected path is connected:

Wolfram Language code: PathGraph[Range[10]]
Wolfram Language code: {PathGraphQ[%], ConnectedGraphQ[%]}
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_2026_connectedgraphq, author="Wolfram Research", title="{ConnectedGraphQ}", year="2010", howpublished="\url{https://reference.wolfram.com/language/ref/ConnectedGraphQ.html}", note=[Accessed: 12-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_connectedgraphq, organization={Wolfram Research}, title={ConnectedGraphQ}, year={2010}, url={https://reference.wolfram.com/language/ref/ConnectedGraphQ.html}, note=[Accessed: 12-June-2026]}