Why are two vertices considered connected in an undirected graph even if there is no direct edge between them?

Conditions

• Applies to undirected graphs.
• Connectivity is judged by the existence of a path, not direct adjacency.

Reasoning, step by step

1. Identify the two vertices in question.
2. Search for a sequence of edges that forms a path from the first vertex to the second.
3. If such a path exists, conclude that the vertices are connected, regardless of whether a direct edge is present.

Example

In the video's example, vertices A and D have no direct edge, but one can travel from A to C, then from C to D. Because the path A -> C -> D exists, A and D are considered connected.

Common misconceptions

• Misinterpreting "connected" as requiring a direct edge between two vertices.
• Assuming that if two vertices are not adjacent, they cannot be part of the same connected component.

Watch the explanation

Explore next

• What is the definition of a connected graph in an undirected graph?
• How many edges does a connected undirected graph with n vertices have at minimum?
• What is a strongly connected graph?