Which of the following vertex sequences is a valid path (not just a walk or trail)?
AA → B → A → C → D
BA → B → C → B → D
CA → C → B → D
DA → B → B → D
A path requires all vertices to be distinct. 'A → C → B → D' visits four distinct vertices in sequence — it is a valid path if those edges exist. Option 0 repeats A; option 1 repeats B; option 3 repeats B immediately (an edge from a vertex to itself would be a loop, not a simple edge). Sequences that repeat vertices are walks or trails, not paths.
Question 2 True / False
If nearly every vertex in a graph has at least one edge (no isolated vertices), then the graph should be connected.
TTrue
FFalse
Answer: False
Having no isolated vertices means every vertex has degree ≥ 1, but that does not guarantee a path between every pair of vertices. For example, the graph {A,B,C,D} with only edges A-B and C-D has no isolated vertices, yet A cannot reach C or D. The graph has two disconnected components. Connectivity is a global property requiring reachability between all vertex pairs, not just local degree conditions.
Question 3 Short Answer
Explain the difference between a walk, a trail, and a path. Why do these distinctions matter for graph theory theorems?
Think about your answer, then reveal below.
Model answer: A walk allows repeated vertices and edges. A trail forbids repeated edges but allows repeated vertices. A path forbids repeated vertices (which also prevents repeated edges). The distinctions matter because theorems are stated in terms of specific types: Euler circuits concern trails (traverse every edge exactly once), Hamiltonian cycles concern paths (visit every vertex exactly once). Using the wrong term leads to applying the wrong theorem.
These are not just terminological nitpicking. An Euler circuit exists iff every vertex has even degree — this is a statement about trails (edge-repetition forbidden), not arbitrary walks. A Hamiltonian cycle is NP-hard to detect in general — this is about paths (vertex-repetition forbidden). The level of restriction changes both the mathematical content and the computational difficulty.