Exercise · ZW-PATH-IN-A-GRAPH-009 · ★★★ Advanced
A graph has edges \(12, 23, 34, 45, 16, 65, 25\). What is the distance (length of a shortest path) between \(1\) and \(4\)?
Choose one option.
Show answer
- C. 3
Explanation
A shortest path is 1, 2, 5, 4 (or 1, 6, 5, 4) of length 3; no path of length 2 exists because 1 and 4 have no common neighbour.
Review the concept: Path in a graph
A path of length \(k\) is a sequence of vertices \(v_0,\dots,v_k\) such that each consecutive pair is joined by an edge of \(E\).
\[\{v_{i-1},v_i\}\in E,\qquad i=1,\dots,k\]
More practice problems: path in a graph
- ZW-PATH-IN-A-GRAPH-001 What is the length of the path 1,2,3,4 in a graph where 12, 23 and 34 are edges?
- ZW-PATH-IN-A-GRAPH-002 A graph has edges 12, 23, 34, 14, 25. Which of these sequences is a path?
- ZW-PATH-IN-A-GRAPH-003 In the 5-cycle 1,2,3,4,5 (edges 12,23,34,45,51), what is the length of the shortest path from 1 to…
- ZW-PATH-IN-A-GRAPH-004 A graph has edges 12, 13, 23, 34. How many walks of length 2 (vertices may repeat) start and end at…
- ZW-PATH-IN-A-GRAPH-005 A path passes through 5 distinct vertices. What is its length?
- ZW-PATH-IN-A-GRAPH-006 Take the graph with edges 12, 23, 34. How many walks of length 3 go from 1 to 2 (vertices may repea…
- ZW-PATH-IN-A-GRAPH-007 What is the maximum length of a path with no repeated vertices in the complete graph K_6?
- ZW-PATH-IN-A-GRAPH-008 If a graph has a path from u to v, what can be guaranteed?