# Chapter 10 notebook: Graph Theory: Structural Tests for Networks

**Goal:** Use a graph obstruction or structure test without mistaking a necessary condition for a proof.

**Start with:** Rules 10.1.1, 10.1.3, 10.3.4. Use a calculator or the optional Python lab. Programming is optional for the workbook; the Jupyter version requires a Python 3 kernel. All lab numbers are constructed practice inputs, not observed data.

**Source:** [Finished Chapter 10](../skills/math-thumb-graph-theory/references/chapter.md) from *Mathematical Rules of Thumb*. Numbered rules, classifications, and the decision path come from the book. The lab, exercises, answer key, and worksheet prompts are companion additions.

## 1. Frame your decision

Write a question in which an answer would change something you do. Gather: Vertices and edges; directed or undirected; simple or multigraph; weights and their signs; connectivity; path versus edge-traversal objective.

- My question and intended decision:
- Known inputs and units:
- Required accuracy or threshold:
- What I expect before calculating:
- What I still need to find out:

Use the lab as a worked starting point if you do not yet have your own problem. For notation or prerequisites, ask the chapter skill to explain only the concept blocking the next step.

## 2. Choose a route

- **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.

**Chapter-specific stop check:** 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.

## 3. Work the lab

Consider the undirected path A-B-C-D. There are four vertices and three edges, so average degree is 2 × 3/4=1.5. A traversal verifies connectedness; together with m=n-1 this proves it is a tree. Vertices A and D have odd degree, so there is an Euler trail from one to the other, but no Euler circuit.

Predict the sign and scale before running the code. Then change one input and explain why the result moves. The code checks the constructed example; it does not prove the rule for every possible input. Code assertions may describe the example's chosen regime, so inspect them before changing that regime.

```python
from collections import deque
graph = {"A": ["B"], "B": ["A", "C"], "C": ["B", "D"], "D": ["C"]}
edge_count = sum(map(len, graph.values()))//2
seen, queue = {"A"}, deque(["A"])
while queue:
    for neighbour in graph[queue.popleft()]:
        if neighbour not in seen:
            seen.add(neighbour)
            queue.append(neighbour)
connected = len(seen) == len(graph)
odd = [v for v, neighbours in graph.items() if len(neighbours)%2]
print("Average degree:", 2*edge_count/len(graph))
print("Connected:", connected, "tree:", connected and edge_count == len(graph)-1)
print("Odd-degree vertices:", odd)
assert sum(map(len, graph.values())) == 2*edge_count
```

**My prediction, observed result, and explanation:**

_Record your work here._

## 4. Practise without the answers

### Exercise 1

A simple graph has four vertices and three edges: a triangle plus an isolated vertex. Is it a tree?

**My approach, assumptions, calculation, and check:**

_Write your attempt here._

### Exercise 2

A simple graph has five vertices and ten edges. Can it be planar?

**My approach, assumptions, calculation, and check:**

_Write your attempt here._

### Exercise 3

Choose a shortest-path method for unit weights, nonnegative unequal weights, and a graph with a negative edge.

**My approach, assumptions, calculation, and check:**

_Write your attempt here._

**Coaching prompt:** “Use the Chapter 10 skill to help me with Exercise 2. Ask for my attempt, give one useful hint if I need it, and help me check the assumptions before showing the answer.”

## 5. Answer key and reasoning

Read this after attempting the exercises, or use it immediately if you prefer a complete walkthrough. An answer is complete only when its assumptions and stopping point are clear.

### Answer 1

No. The count m=n-1 alone is insufficient; it is disconnected and has a cycle.

### Answer 2

No. A simple planar graph with n>=3 has m<=3n-6=9. Exceeding this bound proves nonplanarity.

### Answer 3

Use BFS for unit weights and Dijkstra for nonnegative unequal weights. A negative edge requires a different argument or algorithm, such as Bellman-Ford with negative-cycle checks.

## 6. Build the complete chapter toolkit

The new lab samples the chapter; the following checklist covers all 10 rules. Study one thematic group at a time. A large group can take several sessions.

- **What Edge Counts Reveal:** work with rules 10.1.1, 10.1.2, 10.1.3.
- **Fast Obstruction Tests:** work with rules 10.2.1, 10.2.2, 10.2.3.
- **Traversal and Construction Choices:** work with rules 10.3.1, 10.3.2, 10.3.3, 10.3.4.

For each selected rule, read its equation, explanation, and worked use in the source. Reproduce that example; change one input; then change one assumption so the rule is no longer justified. Record the result and what check catches the failure. Historical examples remain labeled and qualified as in the source.

Read each complete numbered profile in the [chapter reference](../skills/math-thumb-graph-theory/references/chapter.md) before applying it. The cues below abbreviate the graph metadata; they are not complete conditions. Change the status only after doing the practice described below.

| Rule | Book role | First assumptions to inspect | Practice status |
|---|---|---|---|
| 10.1.1: Use handshaking to convert edges into average degree | Independent | finite undirected graph;  loops counted twice in degree | new |
| 10.1.2: Use n-minus-one as the connectedness edge floor | Independent | finite undirected graph;  connected graph | new |
| 10.1.3: Recognize a tree by the n-minus-one edge count plus one condition | Independent | finite connected acyclic graph | new |
| 10.2.1: Test bipartiteness by searching for an odd cycle | Independent | undirected graph | new |
| 10.2.2: Use the planar edge bound as a quick nonplanarity screen | Independent | simple planar graph;  at least three vertices | new |
| 10.2.3: Check Hall bottlenecks before seeking a perfect matching | Independent | finite bipartite graph;  all subsets considered or equivalent certificate | new |
| 10.3.1: Count odd-degree vertices before seeking an Euler trail | Independent | all nonisolated vertices connected;  undirected graph | new |
| 10.3.2: Use maximum degree plus one as a greedy coloring ceiling | Independent | finite simple graph;  proper sequential coloring | new |
| 10.3.3: Use breadth-first search for unweighted shortest paths | Workflow | unweighted or equal weight edges;  finite reachable graph | new |
| 10.3.4: Use Dijkstra only with nonnegative edge weights | Workflow | nonnegative edge weights;  finite graph | new |

For a completed row, record: **rule number / my new input / mathematical claim type / verified assumptions / calculation / check / valid use / rejected use / next step**. “Practised” means you worked an example. “Demonstrated” means you can explain a valid use, transfer it, and reject a misuse without the answer key.

## 7. Apply it to your own problem

Return to your opening question. Choose the smallest rule set that can settle it. Use the book's independent/workflow/specialized classification separately from the claim type (exact, approximate, bound, diagnostic, or heuristic).

- Selected rule number(s) and reason:
- Assumptions that hold, fail, or remain uncertain:
- Substitution with units:
- Result and error, uncertainty, or bound:
- Independent check or limiting case:
- Decision this supports:
- Stop here, do a named next calculation, or gather missing information:

## 8. Transfer and continue

Useful nearby chapters: Chapter 8: number theory; Chapter 9: combinatorics; Chapter 19: optimization. Bring the question, units, assumptions, result type, and uncertainty to the next chapter. Choose a bridge only when it supplies an operation you actually need.

**Completion check:** Explain this chapter's lab in your own words; solve one changed-input exercise; reject one invalid use; and produce a decision record for your own problem. If one check fails, revisit that part of the chapter rather than marking every rule complete.