Step 1 - classify the graph: Identify whether the graph is directed or undirected, weighted or unweighted, simple or non-simple, and connected or disconnected. This step prevents method mismatch because each property changes allowed moves and valid claims. A fast classification at the start saves time and avoids invalid assumptions later.
Step 2 - translate the prompt into traversal language: Convert words into exact objects: walk, path, trail, cycle, tour, subgraph, or spanning tree. The key is to map each condition to a repetition rule about vertices or edges. Once formalized, the problem becomes a constraint-checking task instead of guesswork.
Step 3 - execute and verify constraints: Build the required object and then check every rule explicitly, including start/end conditions and repetition limits. For weighted tasks, compute total cost as over traversed edges and confirm units match the context. Final verification is essential because many incorrect answers are close to valid but break one hidden condition.
| Concept | Can repeat vertices? | Can repeat edges? | Must end where it starts? |
|---|---|---|---|
| Walk | Yes | Yes | No |
| Trail | Yes | No | No |
| Path | No | No | No |
| Cycle | No (except start=end) | No | Yes |
Connected vs complete: A connected graph only requires a path between every pair of vertices, while a complete graph requires a direct edge between every pair. Complete graphs are always connected, but connected graphs are usually far from complete. This distinction matters when deciding whether a missing direct edge is an error or perfectly acceptable.
Tree vs spanning tree: A tree is any connected acyclic graph, whereas a spanning tree is a tree that uses all vertices of a larger graph as a subgraph. Spanning trees remove enough edges to eliminate cycles while preserving reachability. They are used when you want minimum structural complexity without disconnecting the network.
Write definitions with constraint words: Terms like "exactly once," "no repeated vertex," and "returns to start" are the mark-scoring core of graph-theory definitions. If these qualifiers are missing, an answer is often treated as incomplete even if the intuition is right. Memorize compact, precise definitions rather than vague descriptions.
Use a consistency checklist before finalizing: Check direction arrows, edge/vertex repetition rules, and whether the graph type you assumed matches the diagram. For weighted tasks, confirm arithmetic and state total weight clearly with context. A short checklist catches most avoidable losses from misreading.
Exam memory anchor: classify first, translate conditions second, construct third, verify last. This sequence reduces cognitive overload and improves accuracy under time pressure.
Mistaking edge crossings for vertices: Crossing lines in a drawing do not create a vertex unless a node is explicitly marked at the intersection. This misconception changes adjacency and can invalidate every subsequent claim. Always identify vertices by labels or drawn node markers, not by visual crossings alone.
Ignoring direction in digraphs: Students often treat directed edges as bidirectional, which creates invalid walks and false connectivity claims. Direction encodes allowed movement, so traversal must follow arrow orientation exactly. If one-way restrictions are ignored, path existence conclusions become unreliable.
Confusing local and global properties: Seeing many edges near one vertex does not imply the whole graph is connected or complete. Global properties require checking all vertex pairs or all components, not just one region of the graph. Train yourself to separate what is true at one node from what is true for the entire graph.
