graph-algorithms

Problem-solving strategies for graph algorithms in graph number theory

⭐2.2kstars🔀157forks📁View on GitHub🕐Updated Jan 10, 2026

When & Why to Use This Skill

This Claude skill provides advanced problem-solving strategies and computational tools for graph algorithms within the field of graph number theory. It assists researchers and engineers in selecting optimal traversal methods, calculating shortest paths, analyzing network flows, and performing formal verification of graph properties using integrated tools like Sympy and Z3.

Use Cases

  • Algorithm Selection: Determining the most efficient traversal or shortest path algorithm (e.g., Dijkstra vs. Bellman-Ford) based on specific graph constraints and edge weights.
  • Formal Verification: Using Z3-powered tools to prove mathematical conjectures and graph properties, such as the cut property in Minimum Spanning Trees.
  • Spectral Graph Analysis: Computing eigenvalues of adjacency matrices and analyzing connectivity, coloring, and other spectral properties for theoretical research.
  • Network Flow Optimization: Solving complex max-flow/min-cut problems and verifying flow conservation equations in theoretical or logistics models.
namegraph-algorithms
description"Problem-solving strategies for graph algorithms in graph number theory"
allowed-tools[Bash, Read]

Graph Algorithms

When to Use

Use this skill when working on graph-algorithms problems in graph number theory.

Decision Tree

  1. Traversal selection

    • BFS: shortest paths (unweighted), level structure
    • DFS: cycle detection, topological sort, SCC
  2. 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)
  3. Minimum Spanning Tree

    • Prim's: dense graphs, greedy from vertex
    • Kruskal's: sparse graphs, union-find
    • z3_solve.py prove "cut_property"
  4. Network Flow

    • Max-flow = min-cut (Ford-Fulkerson)
    • Matching via flow network
    • sympy_compute.py linsolve "flow_conservation"
  5. 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.