Exercise · ZW-CONNECTED-GRAPH-001 · ★☆☆ Basic
A graph has vertices \(1,2,3,4\) and edges \(12\), \(23\), \(34\). Is it connected?
Choose one option.
Show answer
- A. Yes, because the path \(1,2,3,4\) visits every vertex
Explanation
One path between each pair of vertices is enough; here \(1,2,3,4\) visits them all. Not all edges are needed, and the endpoints have degree 1, not 2.
Review the concept: Connected graph
A graph \(G=(V,E)\) is connected if any two vertices \(u,v\in V\) are joined by a path.
\[\forall\,u,v\in V\ \ \exists\ \text{path from } u \text{ to } v\]
More practice problems: connected graph
- ZW-CONNECTED-GRAPH-002 A graph with vertices 1,dots,5 has edges 12, 23 and 45. How many connected components does it have?
- ZW-CONNECTED-GRAPH-003 A graph with vertices 1,dots,6 has edges 12, 34 and 56. How many connected components does it have?
- ZW-CONNECTED-GRAPH-004 What is the smallest number of edges a connected graph with 8 vertices can have?
- ZW-CONNECTED-GRAPH-005 What is the largest number of edges a graph with 6 vertices can have without being connected?
- ZW-CONNECTED-GRAPH-006 A graph with vertices 1,dots,5 has edges 12, 23, 13 and 45. Which of these edges, once added, makes…
- ZW-CONNECTED-GRAPH-007 A graph with 6 vertices has 11 edges. What can be said?
- ZW-CONNECTED-GRAPH-008 In the cycle 1,2,3,4,5,6,1 (edges 12,23,34,45,56,61) the edges 12 and 45 are removed. How many conn…
- ZW-CONNECTED-GRAPH-009 Let G be a connected graph and e an edge that lies on a cycle of G. After removing e, the resulting…