--- name: math-thumb-graph-theory description: "Apply Chapter 10 (Graph Theory: Structural Tests for Networks) of Mathematical Rules of Thumb to solve, check, or teach problems. Use it to use a graph obstruction or structure test without mistaking a necessary condition for a proof." --- # Graph Theory: Structural Tests for Networks Use this chapter to help the reader make a checked mathematical decision. All 10 numbered rules are available in [the chapter source](references/chapter.md). [The workbook](references/notebook.md) contains a lab, exercises, solutions, and the full rule checklist. [The local rule index](references/rules.json) supplies discovery metadata. ## Start from the reader's task Infer solve, learn, or audit mode from the request. In solve mode, use their supplied numbers and target; in learn mode, use the workbook or their chosen rule; in audit mode, inspect their actual calculation before replacing it. Gather only missing information that changes the choice: Vertices and edges; directed or undirected; simple or multigraph; weights and their signs; connectivity; path versus edge-traversal objective. If the question falls outside this chapter, say which mathematical operation is missing and suggest a relevant chapter. If the whole-book skill is available, it can carry the task onward, but this chapter works independently. ## Select and apply a rule - **Are only $|V|$ and $|E|$ known?** Compute average degree and compare the edge count with $n-1$. These may settle the question before adjacency data is inspected. - **Is a graph at the $n-1$ threshold?** Verify either connectedness or acyclicity. The count alone does not prove it is a tree. - **Is the desired split binary?** Two-color each component. A conflict should be reported with its odd-cycle witness. - **Is a planar drawing requested?** Apply the appropriate edge ceiling first. Failure proves nonplanarity; success merely permits further testing. - **Is the task a one-to-one assignment?** Model a bipartite graph and look for a subset whose neighborhood is too small before attempting exhaustive assignments. - **Must every edge be traversed once?** Count odd degrees and check connectivity among edge-bearing vertices. Do not confuse the task with visiting every vertex once. - **Is a coloring required?** Decide whether a guaranteed $\Delta+1$ construction is sufficient or optimization is worth the additional effort. - **Is the task shortest path?** Equal costs suggest BFS. Unequal nonnegative costs suggest Dijkstra. Any negative weight requires a different correctness argument. Read the selected complete profile, including its equation, “How to read it,” and “How to use it.” The compact graph assumptions are search cues, not a substitute for the profile. Preserve the numbered citation and role. **Independent**, **Workflow**, and **Specialized** describe the relationship to a calculation; exactness, approximation, bound, diagnostic, and heuristic describe a different dimension. Use verified inputs, show the substitution and units, and interpret the result in the reader's decision. Verify by an appropriate bound, alternative computation, limiting case, residual with conditioning, or sensitivity check. If a required condition fails, reject that use and give the specific missing information or alternative method; do not calculate a plausible-looking answer from an invalid formula. **Essential boundary:** The planar edge bound is only a rejection test, and m=n-1 alone does not prove a tree. Separate Euler edge coverage from Hamiltonian vertex coverage. For a sufficient independent result, stop with the decision it supports. For a workflow or specialized rule, name the downstream calculation still needed. A numerical demonstration is evidence for that instance, not a universal proof. ## Teach and check understanding Use the [workbook](references/notebook.md) for guided practice. Start with 10.1.1, 10.1.3, 10.3.4 when the reader wants a starting exercise. Ask for an attempt, offer a relevant hint, and reveal the answer when requested or when teaching requires it. Do not force a quiz when the reader asked for a worked solution. Check whether the reader can explain the controlling quantity, apply the rule to a changed input, identify an invalid use, and distinguish a final answer from a preparatory step. Track only demonstrated work. Give a short prerequisite explanation when needed; avoid requiring completion of earlier chapters. ## Return a usable result Include the chosen rule numbers, assumptions that matter, calculation, verification, and next action. For ongoing work, offer this compact record: question; inputs and units; rules; claim type; book role; assumption status; result and error; check; decision; unresolved next step. Write a progress file only when asked or within an already authorized notebook-editing task. The source chapter is a fixed book snapshot. Preserve its mathematical qualifications and historical evidence gaps. Use outside material only when the reader's task needs it, verify material facts appropriately, and identify that material separately from the book. ## Illustrated exploration Open [the browser reader](assets/reader.html) or [the saved illustrated notebook](assets/notebook.ipynb). [Equation cards](references/equations.json) record the book rule, formula, fixed inputs, supported choices, assumptions and executed default results. - **C10-D01: Test a tree with connectivity and edge count**: rule 10.1.3. - **C10-D02: Close a cycle with two colors**: rule 10.2.1. - **C10-D03: Count odd degrees before planning an Euler trail**: rule 10.3.1. - **C10-D04: Break Dijkstra with one negative edge**: rule 10.3.4. - **C10-D05: See the planar edge bound reject but never certify**: rule 10.2.2. Use a saved illustration only when its conditions fit. Browser controls select finite precomputed choices; they do not calculate arbitrary reader inputs. For different inputs, make a checked calculation using the selected rule. Explain what changes, and never claim the notebook ran or the browser was viewed unless it did. Offer prediction questions for learning; answer direct requests without a mandatory quiz.