Mathematical Rules of Thumb, illustrated reader · Chapter 10

10Graph Theory

Structural Tests for Networks

5 demonstrations follow the chapter's rules. Choose a value, watch the figure and the numbers change, and check your prediction. Every choice is precomputed from the notebook calculations.

Ask the chapter skill

“Help me use Chapter 10 for my question. Choose a rule, check its assumptions, and show how the result changes when an input changes.”

Use math-thumb-graph-theory from the companion's skill package. The demonstrations below also work on their own.

Examples use constructed inputs or the book's own values, disclosed in each panel. A picture illustrates a rule; its assumptions set its scope.

1Demonstration 1 of 5

Test a tree with connectivity and edge count

Why is the triangle-plus-isolate not a tree?

A traversal counts reachable vertices. Compare a path with a triangle plus an isolated vertex, both having three edges.

tree⇔connected and m=n−1 \text{tree}\iff\text{connected and }m=n-1

Graph structure. Simple undirected graphs; four vertices. Layout coordinates are decorative, not edge lengths.

Predict first. Why is the triangle-plus-isolate not a tree?

Choose an example

Test a tree with connectivity and edge count. This graph has 3 edges and 3 reachable vertices. It is not a tree. It has n−1=3 edges but is disconnected, so the edge count alone cannot replace connectivity.
Graph structure: triangle-isolate
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Vertices
4
Edges
3
Reachable from vertex 0
3
Tree
False

This graph has 3 edges and 3 reachable vertices. It is not a tree. It has n−1=3 edges but is disconnected, so the edge count alone cannot replace connectivity.

Use the idea

Use rule 10.1.3 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Simple undirected graphs; four vertices. Layout coordinates are decorative, not edge lengths.

Check your understanding: Why is the triangle-plus-isolate not a tree?
It has n−1 edges but is disconnected and contains a cycle. The edge count alone is insufficient.

Book source: Rule 10.1.3: Recognize a tree by the n-minus-one edge count plus one condition. Demonstration C10-D01. Worked illustration.

2Demonstration 2 of 5

Close a cycle with two colors

Is a five-cycle bipartite?

Alternate colors around a cycle and inspect the final edge. Odd cycles force a conflict.

G bipartite⇔G has no odd cycle G\text{ bipartite}\iff G\text{ has no odd cycle}

Cycle length. Simple undirected cycle graphs. An arbitrary graph requires checking all components.

Predict first. Is a five-cycle bipartite?

Choose an example

Close a cycle with two colors. An alternating two-coloring closes consistently on this even cycle.
Cycle length: 4
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Cycle length
4
Bipartite
True

An alternating two-coloring closes consistently on this even cycle.

Use the idea

Use rule 10.2.1 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Simple undirected cycle graphs. An arbitrary graph requires checking all components.

Check your understanding: Is a five-cycle bipartite?
No. Its odd cycle forces adjacent vertices to receive the same color when alternating two colors.

Book source: Rule 10.2.1: Test bipartiteness by searching for an odd cycle. Demonstration C10-D02. Worked illustration.

3Demonstration 3 of 5

Count odd degrees before planning an Euler trail

Can a triangle with an isolated vertex still have an edge-covering closed trail?

The degree chart is a quick structural check for a route that uses every edge exactly once.

#{v:deg⁡(v) odd}∈{0,2} \#\{v:\deg(v)\text{ odd}\}\in\{0,2\}

Graph structure. All vertices incident to edges must belong to one connected component. Isolated vertices do not matter for using every edge.

Predict first. Can a triangle with an isolated vertex still have an edge-covering closed trail?

Choose an example

Count odd degrees before planning an Euler trail. There are 0 odd-degree vertices. Zero odd vertices: you can walk every edge once and end where you started. Vertex 3 has no edges and is ignored, since the walk only has to cover edges.
Graph structure: triangle-isolate
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Odd-degree vertices
0
Euler trail possible on edge component
True

There are 0 odd-degree vertices. Zero odd vertices: you can walk every edge once and end where you started. Vertex 3 has no edges and is ignored, since the walk only has to cover edges.

Use the idea

Use rule 10.3.1 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

All vertices incident to edges must belong to one connected component. Isolated vertices do not matter for using every edge.

Check your understanding: Can a triangle with an isolated vertex still have an edge-covering closed trail?
Yes. The triangle is the connected edge-bearing component, with all degrees even. It is not a spanning traversal of the isolated vertex.

Book source: Rule 10.3.1: Count odd-degree vertices before seeking an Euler trail. Demonstration C10-D03. Worked illustration.

4Demonstration 4 of 5

Break Dijkstra with one negative edge

Does any negative edge make Dijkstra wrong?

Dijkstra settles the nearest unsettled vertex and never revisits it. That is safe only when no edge can make a later path shorter. A negative edge can sneak in a shortcut after the door is shut.

d(v) final when settled, if all w≥0 d(v)\text{ final when settled, if all }w\ge0

Weight on edge B→A. Directed graph S→A 2, S→B 3, B→A w, A→T 1. Bellman-Ford supplies the true distances.

Predict first. Does any negative edge make Dijkstra wrong?

Choose an example

Break Dijkstra with one negative edge. Dijkstra settles A at length 2 before it looks at B. The detour S→B→A costs 3-0.5=2.5, still longer than 2, so Dijkstra happens to be right. A negative edge removes the guarantee, not every correct answer.
Weight on edge B→A: -0.5
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Weight on B→A
-0.5
Dijkstra distance to T
3
True distance to T
3
Vertices Dijkstra gets wrong
None

Dijkstra settles A at length 2 before it looks at B. The detour S→B→A costs 3-0.5=2.5, still longer than 2, so Dijkstra happens to be right. A negative edge removes the guarantee, not every correct answer.

Use the idea

Use rule 10.3.4 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Directed graph S→A 2, S→B 3, B→A w, A→T 1. Bellman-Ford supplies the true distances.

Check your understanding: Does any negative edge make Dijkstra wrong?
Not always. At w=−0.5 the detour costs 2.5, longer than 2, so the answer is still right. The guarantee is gone, though, and at w=−2 it fails.

Book source: Rule 10.3.4: Use Dijkstra only with nonnegative edge weights. Demonstration C10-D04. Worked illustration.

5Demonstration 5 of 5

See the planar edge bound reject but never certify

K3,3 has 9 edges and the ceiling is 12. Is it planar?

Compare each graph's edge count with the planar ceiling 3n−6. Exceeding it proves nonplanarity; staying under it proves nothing.

G simple planar,n≥3⇒m≤3n−6 G\text{ simple planar},\ n\ge3\ \Rightarrow\ m\le3n-6

Graph. Simple graphs with at least 3 vertices. Triangle-free graphs obey the sharper ceiling 2n−4.

Predict first. K3,3 has 9 edges and the ceiling is 12. Is it planar?

Choose an example

See the planar edge bound reject but never certify. K5 has n=5 and m=10, against the ceiling 3n−6=9. Ten edges exceed nine, so the screen proves K5 is not planar without any drawing.
Graph: K5
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Vertices n
5
Edges m
10
Ceiling 3n−6
9
Screen rejects planarity
True
Actually planar
False

K5 has n=5 and m=10, against the ceiling 3n−6=9. Ten edges exceed nine, so the screen proves K5 is not planar without any drawing.

Use the idea

Use rule 10.2.2 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Simple graphs with at least 3 vertices. Triangle-free graphs obey the sharper ceiling 2n−4.

Check your understanding: K3,3 has 9 edges and the ceiling is 12. Is it planar?
No. The screen passes but cannot certify planarity. The triangle-free ceiling 2n−4=8 is exceeded, so K3,3 is nonplanar.

Book source: Rule 10.2.2: Use the planar edge bound as a quick nonplanarity screen. Demonstration C10-D05. Worked illustration.

Bring the idea to a question of your own

Choose the relationship that answers your question, check its conditions, and compare the result with the accuracy or decision threshold you need.

The chapter skill can adapt these calculations to your inputs. It should name the assumptions, explain what the result supports, and say what still needs evidence. The chapter workbook adds a lab and three exercises with answers.