Questions: Connectivity and Connected Components

Question 1

A social network graph has 1,000 vertices and 3 connected components. What does this tell you?

• A. Exactly 3 vertices are isolated (have no edges connecting them to others)
• B. There are 3 groups of vertices such that paths exist within each group but no path connects any vertex in one group to any vertex in another
• C. The graph has exactly 997 edges, since each component contributes one fewer edge than vertices
• D. Removing any single edge would split the graph into exactly 3 components

Answer: (B)

A connected component is a maximal set of vertices where every pair is connected by a path. Three components mean the 1,000 vertices partition into three groups: paths exist within each group, but no path connects a vertex in one group to any vertex in another. In social network terms, there are three isolated social circles with no links between them. Option A misidentifies isolated vertices with components (a component can be large). Option C misapplies the tree edge-count formula. Option D describes a bridge, which relates to removing one edge from a connected graph — a separate concept.

Question 2

Graph G has vertex connectivity κ(G) = 2 and edge connectivity κ'(G) = 3. What does this tell you about G?

• A. The values are impossible — vertex connectivity always equals edge connectivity in any graph
• B. You need to remove at least 3 edges but only 2 vertices to disconnect G — vertex removal is strictly more powerful because removing a vertex also removes all its incident edges
• C. G has exactly 3 edges and 2 vertices forming its minimum cut
• D. The minimum degree of G is 2, so removing any 3-edge cut automatically removes 2 vertices

Answer: (B)

The inequality κ(G) ≤ κ'(G) ≤ δ(G) holds for all graphs: vertex connectivity is at most edge connectivity, which is at most minimum degree. Removing a vertex deletes all its incident edges simultaneously, making vertex removal at least as powerful as edge removal for disconnecting a graph. Here κ(G) = 2 < κ'(G) = 3 means there exists a set of 2 vertices whose removal disconnects G, but no set of 2 edges can disconnect it — you need 3 edges. These values are entirely consistent with the inequality and show the graph is more vulnerable to targeted vertex removal than to edge removal.

Question 3

A connected graph has exactly one connected component.

• T. True
• F. False

Answer: True

True. A graph is connected if and only if there exists a path between every pair of vertices — which is exactly the condition for all vertices to belong to a single connected component. Connected components partition the vertex set into maximal connected subsets, and a connected graph means this partition has exactly one part: the entire graph. Conversely, a disconnected graph has two or more components, meaning at least one pair of vertices has no connecting path.

Question 4

In a connected graph, there can be at most one path between any pair of vertices.

• T. True
• F. False

Answer: False

False. 'Connected' only requires that at least one path exists between every pair of vertices — it says nothing about uniqueness. Even a simple cycle (triangle) provides two distinct paths between every pair of vertices (clockwise and counterclockwise). Trees are the special case where exactly one simple path exists between every pair of vertices — but that is because trees are connected *and* acyclic. In general, connected graphs can have many paths between any pair, and higher connectivity (more redundant paths) corresponds to greater robustness.

Question 5

Explain the concept of a 'bridge' in a graph and why network designers try to eliminate bridges from critical infrastructure.

Model answer: A bridge is an edge whose removal disconnects the graph — it is the sole connection between two parts of the network. Equivalently, a graph has a bridge if and only if its edge connectivity κ'(G) = 1. In critical infrastructure (internet routing, power grids, transportation networks), a bridge is a single point of failure: if that one cable, road, or link fails, the network splits into isolated components with no alternative route. Network designers eliminate bridges by adding redundant connections, ensuring κ'(G) ≥ 2 so that no single edge failure can disconnect the network.

The practical significance of connectivity measures is greatest in infrastructure design. A network with κ'(G) = 1 is extremely fragile — one cable cut can sever communication between entire regions. Internet backbone networks are designed for high edge and vertex connectivity so traffic can re-route around both accidental failures and targeted attacks. The inequality κ(G) ≤ κ'(G) ≤ δ(G) also warns designers that any node with only one or two connections limits the entire network's connectivity, no matter how well the rest of the graph is connected.