Graph Algorithms
When to Use
Use this skill when working on graph-algorithms problems in graph number theory.
Decision Tree
Traversal selection
- BFS: shortest paths (unweighted), level structure
- DFS: cycle detection, topological sort, SCC
Shortest path algorithms
| Algorithm |
Use Case |
Complexity |
| Dijkstra |
Non-negative weights |
O((V+E) log V) |
| Bellman-Ford |
Negative weights |
O(VE) |
| Floyd-Warshall |
All pairs |
O(V^3) |
Minimum Spanning Tree
- Prim's: dense graphs, greedy from vertex
- Kruskal's: sparse graphs, union-find
z3_solve.py prove "cut_property"
Network Flow
- Max-flow = min-cut (Ford-Fulkerson)
- Matching via flow network
sympy_compute.py linsolve "flow_conservation"
Graph properties
- Spectral: eigenvalues of adjacency matrix
- Connectivity: via DFS/BFS
- Coloring: greedy or SAT reduction
Tool Commands
Sympy_Adjacency
uv run python -m runtime.harness scripts/sympy_compute.py eigenvalues "adjacency_matrix"
Z3_Dijkstra
uv run python -m runtime.harness scripts/z3_solve.py prove "d[v] >= d[u] + w(u,v) for all edges"
Z3_Mst_Cut
uv run python -m runtime.harness scripts/z3_solve.py prove "min_edge_crossing_cut_in_mst"
Sympy_Flow
uv run python -m runtime.harness scripts/sympy_compute.py linsolve "flow_conservation_equations"
Key Techniques
From indexed textbooks:
- [Graph Theory (Graduate Texts in Mathematics (173))] Given two numerical graph invariants i1 and i2, write i1 i2 if we can force i2 to be arbitrarily high on some subgraph of G by assuming that i1(G) is large enough. Formally: write i1 i2 if there exists a function f : N → N such that, given any k ∈ N, every graph G with i1(G) f (k) has a subgraph H with i2(H) k. If i1 i2 as well as i1 i2, write i1 ∼ i2.
- [Graph Theory (Graduate Texts in Mathematics (173))] Find the smallest integer b = b(k) such that every graph of order n with more than kn + b edges has a (k + 1)-edge- connected subgraph, for every k ∈ N. Show that every tree T has at least Δ(T ) leaves. Show that a tree without a vertex of degree 2 has more leaves than other vertices.
- [Graph Theory (Graduate Texts in Mathematics (173))] For every n > 1, nd a bipartite graph on 2n vertices, ordered in such a way that the greedy algorithm uses n rather than 2 colours. Exercises Consider the following approach to vertex colouring. First, nd a max- imal independent set of vertices and colour these with colour 1; then nd a maximal independent set of vertices in the remaining graph and colour those 2, and so on.
- [Graph Theory (Graduate Texts in Mathematics (173))] Show that, for every r ∈ N, every innite graph of upper density s subgraph for every s ∈ N. Deduce that the upper density of innite graphs can only take r−1 has a K r the countably many values of 0, 1, 1 2 , 2 3 , 3 4 Extremal Graph Theory Given a tree T , nd an upper bound for ex(n, T ) that is linear in n and independent of the structure of T , i. Prove the Erd˝os-S´os conjecture for the case when the tree considered is a star.
- [Graph Theory (Graduate Texts in Mathematics (173))] Colouring Slightly more generally, a class G of graphs is called χ-bounded if there exists a function f : N → N such that χ(G) f (r) for every graph G ⊇ Kr in G. In such graphs, then, we can force a Kr subgraph by making χ larger than f (r). Show that the four colour theorem does indeed solve the map colouring problem stated in the rst sentence of the chapter.
Cognitive Tools Reference
See .claude/skills/math-mode/SKILL.md for full tool documentation.
Source: parcadei/Continuous-Claude-v3 → .claude/skills/math/graph-number-theory/graph-algorithms/SKILL.md
1---
2name: graph-algorithms
3description: "Problem-solving strategies for graph algorithms in graph number theory"
4allowed-tools: "[Bash, Read]"
5category: general-purpose
6source_repo: parcadei/Continuous-Claude-v3
7source_path: ".claude/skills/math/graph-number-theory/graph-algorithms/SKILL.md"
8source_url: https://github.com/parcadei/Continuous-Claude-v3/blob/HEAD/.claude/skills/math/graph-number-theory/graph-algorithms/SKILL.md
9metadata:
10 source: https://skillmd.com/skills/parcadei/graph-algorithms
11---
12
13
14# Graph Algorithms
15
16## When to Use
17
18Use this skill when working on graph-algorithms problems in graph number theory.
19
20## Decision Tree
21
22
231. **Traversal selection**
24 - BFS: shortest paths (unweighted), level structure
25 - DFS: cycle detection, topological sort, SCC
26
272. **Shortest path algorithms**
28 | Algorithm | Use Case | Complexity |
29 |-----------|----------|------------|
30 | Dijkstra | Non-negative weights | O((V+E) log V) |
31 | Bellman-Ford | Negative weights | O(VE) |
32 | Floyd-Warshall | All pairs | O(V^3) |
33
343. **Minimum Spanning Tree**
35 - Prim's: dense graphs, greedy from vertex
36 - Kruskal's: sparse graphs, union-find
37 - `z3_solve.py prove "cut_property"`
38
394. **Network Flow**
40 - Max-flow = min-cut (Ford-Fulkerson)
41 - Matching via flow network
42 - `sympy_compute.py linsolve "flow_conservation"`
43
445. **Graph properties**
45 - Spectral: eigenvalues of adjacency matrix
46 - Connectivity: via DFS/BFS
47 - Coloring: greedy or SAT reduction
48
49
50## Tool Commands
51
52### Sympy_Adjacency
53```bash
54uv run python -m runtime.harness scripts/sympy_compute.py eigenvalues "adjacency_matrix"
55```
56
57### Z3_Dijkstra
58```bash
59uv run python -m runtime.harness scripts/z3_solve.py prove "d[v] >= d[u] + w(u,v) for all edges"
60```
61
62### Z3_Mst_Cut
63```bash
64uv run python -m runtime.harness scripts/z3_solve.py prove "min_edge_crossing_cut_in_mst"
65```
66
67### Sympy_Flow
68```bash
69uv run python -m runtime.harness scripts/sympy_compute.py linsolve "flow_conservation_equations"
70```
71
72## Key Techniques
73
74*From indexed textbooks:*
75
76- [Graph Theory (Graduate Texts in Mathematics (173))] Given two numerical graph invariants i1 and i2, write i1 i2 if we can force i2 to be arbitrarily high on some subgraph of G by assuming that i1(G) is large enough. Formally: write i1 i2 if there exists a function f : N → N such that, given any k ∈ N, every graph G with i1(G) f (k) has a subgraph H with i2(H) k. If i1 i2 as well as i1 i2, write i1 ∼ i2.
77- [Graph Theory (Graduate Texts in Mathematics (173))] Find the smallest integer b = b(k) such that every graph of order n with more than kn + b edges has a (k + 1)-edge- connected subgraph, for every k ∈ N. Show that every tree T has at least Δ(T ) leaves. Show that a tree without a vertex of degree 2 has more leaves than other vertices.
78- [Graph Theory (Graduate Texts in Mathematics (173))] For every n > 1, nd a bipartite graph on 2n vertices, ordered in such a way that the greedy algorithm uses n rather than 2 colours. Exercises Consider the following approach to vertex colouring. First, nd a max- imal independent set of vertices and colour these with colour 1; then nd a maximal independent set of vertices in the remaining graph and colour those 2, and so on.
79- [Graph Theory (Graduate Texts in Mathematics (173))] Show that, for every r ∈ N, every innite graph of upper density s subgraph for every s ∈ N. Deduce that the upper density of innite graphs can only take r−1 has a K r the countably many values of 0, 1, 1 2 , 2 3 , 3 4 Extremal Graph Theory Given a tree T , nd an upper bound for ex(n, T ) that is linear in n and independent of the structure of T , i. Prove the Erd˝os-S´os conjecture for the case when the tree considered is a star.
80- [Graph Theory (Graduate Texts in Mathematics (173))] Colouring Slightly more generally, a class G of graphs is called χ-bounded if there exists a function f : N → N such that χ(G) f (r) for every graph G ⊇ Kr in G. In such graphs, then, we can force a Kr subgraph by making χ larger than f (r). Show that the four colour theorem does indeed solve the map colouring problem stated in the rst sentence of the chapter.
81
82## Cognitive Tools Reference
83
84See `.claude/skills/math-mode/SKILL.md` for full tool documentation.
85
86---
87
88**Source:** [`parcadei/Continuous-Claude-v3`](https://github.com/parcadei/Continuous-Claude-v3) → `.claude/skills/math/graph-number-theory/graph-algorithms/SKILL.md`