Day 24 — Graph Modeling & Gate VI

Updated

July 30, 2025

Day 24 — Graph Modeling & Gate VI

Day 68 — Graphs in CS

Stage VI · concept day
Goal: Map common CS structures to graphs; use a modeling checklist; choose the right question (path, color, topo, matching, MST, short path); complexity culture (P vs NP names where Hamilton-relevant).

Why this matters

Stage VI tools only pay off when you recognize a graph in the wild and ask a precise question. Today is a pattern catalog: dependency graphs, call graphs, CFGs, social graphs, routing nets, state-transition systems—and a disciplined modeling checklist for Day 69 workshop and Gate VI.

Theory

Modeling checklist

When a word problem appears:

  1. What are the vertices? (Be concrete: packages, functions, basic blocks, people, routers, states.)
  2. What are the edges? Directed? Weighted? Multi?
  3. What property matters? Connectivity, cycles, order, distance, cut, matching, coloring, Euler/Hamilton…
  4. Which algorithm/theorem applies? BFS/DFS, topo, Dijkstra, Hall, Euler degrees, greedy color…
  5. Complexity reality: is the question poly-time solvable on this class, or hard (Hamilton/TSP/coloring general)?
  6. Sanity: tiny instance; does the model over/under-fit semantics?

Catalog of CS graphs

Dependency graphs

  • Vertices: packages, modules, tasks, build targets.
  • Arcs: “\(A\) depends on \(B\)” (orient \(A\to B\) or \(B\to A\) consistently—state convention: often “must build \(B\) before \(A\)” as \(B\to A\)).
  • Questions: cycle? (circular depends); topological install/build order; longest path = critical compile chain.
  • Tools: DAG check, Kahn/DFS topo, longest path DP.

Call graphs

  • Vertices: functions/methods.
  • Arcs: \(f\to g\) if \(f\) may call \(g\).
  • Questions: reachability (dead code?); strongly connected components (mutual recursion clusters); dominating entry points.
  • Tools: DFS/BFS, SCC condensation DAG.

Control-flow graphs (CFG)

  • Vertices: basic blocks.
  • Arcs: possible control transfers.
  • Questions: dominators; loops (back edges in DFS); reachability; path-sensitive analysis limits.
  • Tools: DFS edge types; dominator trees (awareness); not all paths feasible (semantics).

Social / trust graphs

  • Vertices: users.
  • Edges: friendship undirected; follow directed.
  • Questions: distance (degrees of separation); communities; influencers (degree/centrality); bridges.
  • Tools: BFS distance; cut vertices; bipartite user–content for recommendations.

Routing / computer networks

  • Vertices: routers/hosts.
  • Edges: links with latency/bandwidth weights.
  • Questions: shortest path; MST for broadcast trees; connectivity/fault tolerance (bridges).
  • Tools: Dijkstra/BFS; Kruskal/Prim; edge connectivity culture.

State-transition systems

  • Vertices: states of a protocol/FSM.
  • Arcs: labeled transitions.
  • Questions: reachable states; cycles (livelock/loops); shortest event sequence to a goal.
  • Tools: BFS on state graph; exponential state spaces (Day 53 counting!).

Interference / conflict graphs

  • Vertices: variables, exams, frequencies.
  • Edges: conflict.
  • Questions: chromatic number / coloring; clique lower bound.
  • Tools: greedy color; exact hard in general; special graph classes.

Bipartite incidence graphs

  • Parts: jobs/machines, clients/servers, documents/terms.
  • Questions: matching assignment; Hall feasibility.
  • Tools: matching algorithms; Hall check small cases.

Choosing a question (quick table)

English ask Graph question
Can X affect Y? Path / reachability
Circular dependency? Directed cycle
Valid order? Topological order
Fewest hops? BFS distance
Fastest with weights? Dijkstra/BF
Wire all sites cheaply? MST
Assign without conflict? Coloring / matching
Tour every road? Euler
Tour every city? Hamilton/TSP (hard)
Bottleneck person? Cut vertex

Complexity culture (names only where useful)

Problem Typical complexity culture
Connectivity, BFS/DFS, Dijkstra (nonneg), MST, Euler, bipartite matching, topo on DAG Polynomial (efficient)
Hamilton path/cycle, TSP, general coloring \(\chi\le k\) (\(k\ge 3\)), longest path general NP-hard / NP-complete decide
Planarity testing Polynomial (surprising historically)
4-color planar Always yes (theorem)—not a search for \(k=4\) decision on planar

Moral: model carefully—if you reduced your product feature to Hamilton, expect pain; if to BFS, ship it.

Weighted vs unweighted; directed vs undirected

Mis-orienting edges or forgetting weights is the #1 modeling bug. Write \(G=(V,E)\) explicitly once.

Multi-layer models

Sometimes you need two graphs (e.g. physical network + logical overlay). Don’t smash them without labeling.

Worked examples

Example 1 — Package manager

\(V=\) packages; arc \(A\to B\) if \(A\) requires \(B\) built first… Use topo for install; cycle = error.

Example 2 — Makefile

Targets and prerequisites: DAG ideally; make walks dependency graph.

Example 3 — Dead function

Call graph: functions not reachable from main / exports—DFS mark.

Example 4 — Infinite loop structure

CFG back edge to ancestor ⇒ loop in flowgraph (semantic nontermination needs more).

Example 5 — Friend recommendations

Undirected social: distance-2 vertices as candidates.

Example 6 — Network outage

Bridge edge: link whose failure disconnects—identify cut edges.

Example 7 — Protocol reachability

State machine 12 states: BFS from init; count reachable ≤12.

Example 8 — Exam schedule

Courses vertices; edge if shared student; \(\chi\) = min slots.

Example 9 — Job assignment

Bipartite workers–jobs; max matching.

Example 10 — Delivery

City graph weights travel time; Dijkstra warehouse to client.

Example 11 — Fiber backbone

Connect sites min cable: MST.

Example 12 — Garbage truck

Street edges must be traversed: Chinese Postman / Euler if even degrees.

Example 13 — Travel itinerary all cities

Hamilton/TSP—hard; use heuristics.

Example 14 — Register allocation

Interference graph coloring (Day 67).

Example 15 — Type of mistake

Using undirected graph for one-way streets: wrong reachability.

Exercises

  1. Write the modeling checklist from memory.
  2. Model npm/pip dependencies; what does a cycle mean?
  3. Model a CFG for a for loop with break—vertices/edges.
  4. Call graph vs CFG: one sentence difference.
  5. Social: define diameter of a friend graph.
  6. Network: when BFS vs Dijkstra.
  7. FSM: why state graph can be huge (product of variables).
  8. Exam coloring: construct conflict graph from a small table of student enrollments.
  9. Matching: 3 jobs 3 machines constraints—Hall check.
  10. Classify: “visit every city once” vs “traverse every road once.”
  11. Name a poly-time problem and an NP-hard problem from the table.
  12. Orient package depends two ways; show how topo meaning flips.
  13. MST vs shortest path tree: different goals—example.
  14. SCC in call graphs: mutual recursion cluster meaning.
  15. CS security: attack graph awareness (vertices states/privileges).
  16. Data lineage graph: path = provenance.
  17. Git commits DAG: merge parents—not a tree.
  18. True/false: every web link graph is a DAG.
  19. Choose tools for “critical path of project tasks.”
  20. Choose tools for “assign radio channels without interference.”
  21. Invent a CS scenario for bipartite matching.
  22. Invent a CS scenario that is wrongly modeled as Hamilton.
  23. Complexity: why 2-coloring easy but 3-coloring hard (culture).
  24. Multi-model: physical + logical network—what edges differ?
  25. One-page map: Stage VI algorithm → CS use case (fill table).

CS connection

This day is the CS connection. Capstone modeling (later) should reuse this catalog.

Common pitfalls

Pitfall What to do instead
Vague vertices (“the system”) Name atomic entities
Wrong direction on depends Write English for each arc
Asking Hamilton when Euler fits Edges vs vertices tours
Ignoring weights State unweighted hops vs cost
Exponential state spaces surprise Count first (Day 53)

Checkpoint

  • Checklist cold
  • 6 catalog types with vertex/edge/question
  • Poly vs NP-hard examples
  • Exercises 1–15
  • One original model written fully
  • Ready for modeling workshop

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. Call graph: functions; CFG: basic blocks within/between.
  2. Hamilton vs Euler.
  3. BFS poly; Hamilton NP-complete.
  4. False—cycles everywhere.
  5. DAG longest path.
  6. Graph coloring.

Deepening notes

One-page algorithm→use map (fill)

Algorithm/theorem CS use
BFS
DFS / topo
Dijkstra
Kruskal/Prim
Matching/Hall
Coloring
Euler
Hamilton/TSP

Anti-catalog (wrong tools)

Ask Wrong tool Right tool
Min hops Dijkstra with random weights BFS
Build order Undirected connected DAG topo
Assign one job each Coloring Matching
Street sweep Hamilton Euler

Extra scenario drills

D1. Kubernetes service mesh latency—shortest path.
D2. Monorepo package graph—cycle CI fail.
D3. Classroom seating conflicts—coloring.
D4. Bike share stations rebalance—transport, not pure graph.
D5. Privilege escalation paths—attack graph reachability.
D6. CDN cache hierarchy—tree.
D7. Microservices rate-limit dependency—DAG critical.
D8. P2P overlay vs underlay—two graphs.

Flash checklist

V? E directed/weight? Question? Tool? Complexity? Sanity?

Exam drill block

E1. Model “courses with prerequisites” as a digraph; name the cycle question and the linearization question.
E2. Model “servers and latency links” for min-delay routing—weighted shortest path.
E3. Model “jobs and machines, each job one machine” as bipartite matching.
E4. Model “register interference” as coloring; \(\chi\) = min registers.
E5. Model “street sweeping” vs “visit each landmark once”—Euler vs Hamilton.
E6. Call graph vs control-flow graph: different \(V\) definitions.
E7. Poly-time: BFS connectivity; hard: Hamilton cycle—one sentence each.
E8. Package lockfile: DAG check fails ⇒ circular dependency error.
E9. True/false: (i) every CS graph problem is poly-time (ii) undirected topo order (iii) matching ≠ coloring.
E10. Write \(V\), \(E\), directed?, weighted?, question for a social “friend suggestion via common neighbors.”

Mini solutions

E1. \(V=\) courses; arc \(A\to B\) if \(A\) prereq of \(B\); cycle = impossible plan; topo = valid term order.
E5. Euler: edges (streets); Hamilton: vertices (landmarks).
E9. F; F (needs DAG/directed); T.
E10. \(V=\) users; undirected edges = friendship; question e.g. score common neighbors for non-adjacent pairs.

Complexity postcard

Easy (poly, typical) Hard (NP-complete classically)
Connectivity, BFS/DFS Hamilton path/cycle
Shortest path \(w\ge 0\) Longest path (general)
MST TSP
2-color / bipartite \(k\)-color \(k\ge 3\)
Matching bipartite …

Synthesis

CS graph work is model then ask. Wrong \(V\)/\(E\) choice is the usual bug—not the algorithm. Match the question to BFS, Dijkstra, topo, MST, matching, coloring, Euler, or “this is Hamilton/TSP hard.” Count state spaces when the graph is implicit (Day 53). Day 69 practices full writeups.

S1. Three original systems → full \(G=(V,E)\) + question + tool.
S2. One anti-model: show a wrong graph that invites the wrong algorithm.
S3. Cold: checklist six items without notes.
S4. Implicit graph: configuration space of a puzzle—when is BFS feasible?
S5. Pick one hard problem (TSP / Hamilton) and state the honest poly-time relaxation you would ship.

Tomorrow

Day 69 — Modeling workshop: 8–12 word problems → formal \(G=(V,E)\) + precise questions.

Day 69 — Modeling workshop

Stage VI · workshop day
Goal: Convert 8–12 word problems into formal \(G=(V,E)\) plus precise questions (path, color, topo, matching, short path, Euler/Hamilton, tree/MST); practice the writeup template for Gate VI.

Why this matters

Gate VI and real engineering reviews reward clear models, not vague gestures. Today is deliberate practice: every problem gets the same template until it is automatic.

Writeup template (required format)

For each problem, write:

Name:
Vertices V:
Edges/Arcs E: (directed? weighted?)
Graph class notes: (simple/multi/bipartite/DAG candidate…)
Question(s) in graph language:
Method/tool:
Answer or plan (hand-solvable instance if numbers given):
Pitfall / alternative model:

Method selection guide (Stage VI)

Story cue Model & tool
Prerequisites / build order DAG + topo
Circular depends Directed cycle detect
Fewest hops BFS
Min time/cost paths Dijkstra / BF
Wire all cheaply MST Kruskal/Prim
Conflicts / slots Coloring
Assign jobs one-to-one Bipartite matching + Hall
Tour every street Euler
Tour every city Hamilton (hard)
Hierarchy unique paths Tree checks
Reliability single point Cut vertex/edge

Warm-up models (short)

W1. Five courses; prereq list.
W2. Four friends; friendships; distance between A and D.
W3. Three variables live ranges overlapping.

W4. Delivery truck must drive every street downtown at least once.
W5. Sales rep must visit each client city exactly once and return.

Workshop problems

Solve at least 8 in full template form; stretch for 12.

Set A — Dependencies & order

A1. Software packages. Packages {P,Q,R,S}; depends: P→Q, P→R, Q→S, R→S (arc means “uses”). Is install-by-topo possible? List a valid order if we orient “build dependency first” consistently—state orientation.

A2. Project tasks. Tasks A(2d), B(3d), C(1d), D(4d), E(2d); precedences A before C, B before C, C before E, D before E. Model DAG; find critical path length.

A3. Spreadsheet. Cells A1, B1, C1 with formulas A1=B1+1, B1=C1+1, C1=A1+1. Model; diagnose.

Set B — Networks & paths

B1. Subway. Stations S,A,B,C,T with undirected edges as Day 62 G1. Fewest hops S to T?

B2. Weighted roads. Same vertices; weights as Day 64 Ex.1. Min driving time S to T?

B3. Fiber. Towns 1..5; possible links with costs you choose; connect all min cost—MST.

B4. One-way streets. Directed city; weak vs strong connectivity question.

Set C — Assignment & conflict

C1. Jobs/machines. Jobs J1–J3, machines M1–M3; edges for compatible pairs (specify); Hall check for full assignment.

C2. Exam scheduling. Courses {1,2,3,4}; conflicts {12,23,34,14}; min exam slots = \(\chi\).

C3. Register lite. Variables a,b,c,d; overlaps ab,bc,cd,ac; registers needed.

Set D — Tours & structure

D1. Snowplow. City graph degrees all even except two; what tour exists?

D2. Sales route. 5 cities complete graph—name the hard problem.

D3. Tree check. n=6, edges 5, connected—tree? Unique path?

D4. Bipartite zoo. Animals–habitats incidence; matching interpretation.

Set E — Systems & states

E1. Protocol. States {Idle, Auth, Active, Error}; transitions Idle→Auth→Active→Idle, Auth→Error→Idle. Reachable from Idle? Cycles?

E2. Feature flags. 3 flags; transitions flip one bit; state graph is 3-cube—diameter?

E3. Call graph. Functions main, f, g, h; calls main→f, f→g, g→f, main→h. SCCs? Dead code?

Set F — Rapid modeling (template skeleton only)

For each, fill V, E meaning, question type in ≤4 lines.

F1. Classroom seats; two students cannot sit adjacent if they conflict—assign seats?
F2. Airline crews; flights as vertices; edge if same-day overlap—crew count?
F3. Makefile targets and dependencies.
F4. Escape routes from building floor plan (portals as edges).
F5. Matching interns to projects with skill edges.
F6. Chip modules; wires as edges; can you draw with no crossing? (planarity ask)

Worked solutions (selected)

A1. Orient arc \(X\to Y\) if \(X\) must be installed before \(Y\) (i.e. \(Y\) depends on \(X\)): if P depends on Q and R, then Q→P, R→P, etc. Rebuild from English carefully. Suppose depends “P requires Q and R; Q requires S; R requires S”: arcs S→Q, S→R, Q→P, R→P. Topo: S, Q, R, P or S, R, Q, P. No cycle.

A2. Longest path: e.g. B(3)–C(1)–E(2)=6 or D(4)–E(2)=6 or A(2)–C–E=5. Critical length 6.

A3. Cycle A1–B1–C1–A1: circular reference; not a DAG.

B1. dist=2 via S–B–T.

B2. d(T)=5 path S–A–B–C–T.

C2. Conflict = C_4: \(\chi=2\).

C3. Interference path/cycle: a–b–c–d + a–c ⇒ odd structure; \(\chi=3\) (triangle a,b,c).

D1. Eulerian trail between the two odd-degree vertices.

D2. TSP / Hamilton cycle optimization.

D3. Yes tree if connected with 5 edges on 6 verts.

E3. SCC {f,g}; {main}; {h}; all reachable from main except nothing dead if all called; h leaf.

Self-score

Set Min problems Points Score
A 2 15 /15
B 2 15 /15
C 2 15 /15
D 2 15 /15
E 1 10 /10
Template quality all 30 /30
Total 100 /100

Pass ≥ 75. Template quality: clear V, E, question, method.

Exercises (complete the rest)

  1. Full template for A1–A3.
  2. Full template for B1–B4.
  3. Full template for C1–C3.
  4. Full template for D1–D4.
  5. Full template for E1–E3.
  6. Invent a dependency problem with a cycle; show Kahn fails.
  7. Invent a matching problem that fails Hall; exhibit \(S\).
  8. Model DNS hierarchy as a tree; what do cuts mean?
  9. Model git commits with merges as DAG; topo = ?
  10. Why CFG path count ≠ test adequacy alone.
  11. Convert social “influencer” into degree + betweenness awareness.
  12. MST vs TSP on same towns—different questions.
  13. Color a conflict graph from a real weekly schedule of yours.
  14. Dijkstra on a 5-vertex digraph you create.
  15. Euler or Hamilton: museum hallway vs city landmarks.
  16. State explosion: 10 boolean vars → how many states?
  17. Bridge in a company org chart modeled as graph.
  18. Peer review: swap models with a peer (or future you) and critique.
  19. Challenge: model MapReduce / dataflow as DAG; critical path.
  20. Write Gate VI modeling section practice under 25 minutes.
  21. List 5 mistakes from your first drafts.
  22. Redo worst writeup.
  23. Connect one model to Day 53 counting (state space size).
  24. Connect one model to Day 65 Hall.
  25. One-page portfolio of 3 best models for Gate VI.

CS connection

Workshop scenarios are drawn from engineering practice. Carry the template into design docs: “Vertices are… Edges mean… We ask…”

Common pitfalls

Pitfall What to do instead
Missing direction Always say directed/undirected
Question in English only Translate to path/color/…
Over-large model Minimal V that captures the ask
Solving without model Template first, numbers second
Hard problem when easy fits Recheck Euler vs Hamilton etc.

Checkpoint

  • Template automatic
  • ≥ 8 full writeups
  • Self-score ≥ 75
  • One dependency + one matching + one short path
  • One hard-vs-easy tour contrast
  • Portfolio of 3 models ready for Gate VI

Two personal takeaways:

  1. …
  2. …

Deepening notes

Template speed run (5 min each)

Practice blank template fills:

  1. npm depends
  2. subway hops
  3. exam conflicts
  4. job matching
  5. weighted roads
  6. snowplow
  7. FSM protocol
  8. MST fiber

Peer critique rubric

Item 0–2 pts
V precise
E meaning clear
Question graph-theoretic
Method fits
Answer/plan correct

Extra invented problems

I1. Hospital rooms & equipment sterilization constraints.
I2. Compiler basic-block scheduling with latencies.
I3. Social “block” undirected vs “mute” directed.
I4. Warehouse robots aisle graph Euler.
I5. Course waitlist matching bipartite.

Gate VI modeling preview

You will need: one full package/exam/matching model; one shortest-path or MST numeric; Euler vs Hamilton paragraph. Prepare three templates tonight.

Timed set (40 minutes)

Do full templates for:

  1. A1 packages
  2. B2 weighted roads
  3. C2 exams
  4. C1 matching
  5. D1 snowplow
  6. E1 protocol
  7. Invent MST fiber 5 towns
  8. Invent call graph SCC

Score: 5 pts template structure + 5 pts correct analysis each = /80.

Common template failures checklist

  • Forgot directed vs undirected
  • Edges mean two different English things
  • Question left in English only
  • Used Hamilton for street traversal
  • Dijkstra on unweighted hops
  • Topo on undirected graph
  • Hall without checking all \(S\)
  • No small sanity instance

Three portfolio models (finalize tonight)

Portfolio 1 — Dependencies
Portfolio 2 — Assignment/matching
Portfolio 3 — Routing/shortest path

Write each to Gate quality; bring into Day 70.

Fully worked templates (exam quality)

W4 — Snowplow / streets.

Name: Downtown street inspection
Vertices V: intersections
Edges E: undirected streets (multiedges if needed)
Question: Euler trail/circuit?
Method: count odd-degree vertices; Hierholzer if 0 or 2 odds
Pitfall: modeling as Hamilton (cities) instead of edges

W5 — Sales tour.

Name: Client tour
Vertices V: client cities (+ depot)
Edges E: roads (often complete weighted)
Question: Hamilton cycle / TSP
Method: small n backtrack; large n heuristics; not Euler
Pitfall: calling it Chinese postman

C1 sketch. Bipartite \(L=\) jobs, \(R=\) machines; edge = compatible. Hall on all \(S\subseteq L\). Max matching algorithm if numbers given.

A3 full. Cells form directed graph formula-reference; cycle ⇒ circular reference; topo sort impossible; spreadsheet engine error.

Deep dive — Minimal models

Good models omit irrelevant detail. If the question is only “can we order builds?”, weights do not matter—use an unweighted DAG. If the question is “min travel time,” unweighted BFS is wrong—use Dijkstra. If conflicts are the only constraint, coloring needs no distances. Ask what decision changes if you delete a feature from the model. If none, delete it.

Synthesis — Gate VI writeup muscle

  1. Template first, always.
  2. Name graph class (DAG, bipartite, weighted, …).
  3. Translate the English ask into path / color / match / Euler / Hamilton / MST / topo.
  4. Pick the lightest correct algorithm/theorem.
  5. Sanity on a tiny instance.
  6. Note the classic mix-up (Euler↔︎Hamilton, BFS↔︎Dijkstra, undirected↔︎directed).

S1. Full template + solution plan for A2 critical path.
S2. Full template for C2 exam \(\chi\).
S3. Full template for D1 snowplow.
S4. Invent and template a problem that looks like Hamilton but is Euler.
S5. One-page portfolio: dependency + matching + shortest path, Gate-ready.

Tomorrow

Day 70 — Gate VI: model + handshaking + tree check + BFS levels + DAG topo + bipartite/matching + shortest path on a tiny weighted graph.

Day 70 — Gate VI

Stage VI · gate day
Goal: Demonstrate graph literacy: definitions, handshaking, connectivity, trees, BFS/DFS, DAGs/topo, Dijkstra sketch, bipartite/matching lite, Euler/Hamilton awareness, coloring/planarity culture, and CS modeling. Required: model + handshaking + tree check + BFS levels + DAG topo + one bipartite/matching + shortest path numbers on a tiny weighted graph.

Why this matters

Capstone work needs one solid graph model of a CS-ish situation. This gate certifies you can build and analyze such models under mild time pressure—definitions, structure, algorithms, and modeling together.

How to take this gate

  1. Timebox ~100–130 minutes optional.
  2. Closed notes first pass.
  3. Every modeling item needs the Day 69 writeup template.
  4. Score with rubric; remediate below-threshold sections within 48h.
Important

No coding labs. Hand-simulate algorithms with tables. Proofs short and complete.

Rubric

Section Points Pass bar
A Definitions 15 ≥ 11
B Structure (degree, paths, trees) 20 ≥ 14
C Algorithms (BFS/DFS/topo/Dijkstra) 25 ≥ 18
D Advanced awareness 15 ≥ 10
E Modeling portfolio 25 ≥ 18
Total 100 ≥ 75, no section < 50%

Theory — rapid self-check

Reproduce from memory:

  1. Simple undirected graph; directed graph.
  2. Handshaking lemma + odd-degree corollary.
  3. Walk / trail / path / cycle.
  4. Connected component; distance; diameter.
  5. Tree TFAE (at least 3 characterizations).
  6. BFS shortest hops; DFS disc/fin idea.
  7. DAG ⇔ topological order exists.
  8. Dijkstra needs nonnegative weights.
  9. Bipartite ⇔ no odd cycle; matching; Hall statement.
  10. Euler circuit iff all even degrees; Hamilton hard.
  11. \(\chi\ge\omega\); planar ⇒ \(\chi\le 4\).
  12. Modeling checklist.

Gate exam (closed book)

Section A — Definitions (15)

Write precise definitions (≈2 pts each):

  1. Simple undirected graph \(G=(V,E)\).
  2. Degree; handshaking lemma.
  3. Path vs cycle.
  4. Connected component.
  5. Tree (two equivalent definitions).
  6. DAG and topological order.
  7. (Bonus) Proper vertex coloring; \(\chi(G)\).

Section B — Structure (20)

  1. Degrees \(3,3,2,2,2,2\): number of edges? Possible simple? Number of odd-degree vertices?
  2. Prove number of odd-degree vertices is even.
  3. Connected graph on 9 vertices with 9 edges: must it contain a cycle? Why?
  4. Forest: 15 vertices, 4 components: edges?
  5. Distance and diameter of \(C_6\).
  6. Unique path property: state and use to show a given small graph is/is not a tree.
  7. Directed: in- and out-degree sums equal \(|E|\)—prove in one line.

Section C — Algorithms (25)

Use this undirected graph unless stated:
Vertices \(S,A,B,C,T\). Edges: \(S{-}A,S{-}B,A{-}B,A{-}C,B{-}C,B{-}T,C{-}T\).
Neighbor order: alphabetical.

  1. BFS from \(S\): discovery order, dist, parents; list levels.
  2. DFS from \(S\) (alphabetical): discovery order, parents (disc/fin optional but good).
  3. Is the graph bipartite? Justify (odd cycle?).
  4. Directed version: orient every edge toward the alphabetically later endpoint; compute a topological order or show a cycle.
  5. Weights: \(SA=2,SB=5,AB=1,AC=4,BC=1,BT=3,CT=1\). Dijkstra from \(S\) to \(T\): final dist and path.
  6. Kahn: on DAG with arcs \(A\to C,B\to C,C\to D,A\to D\)—full in-degree trace and one topo order.

Section D — Advanced awareness (15)

  1. Euler: does \(K_4\) have an Eulerian circuit? Eulerian trail?
  2. Hamilton: does \(K_{2,3}\) have a Hamiltonian cycle? Path?
  3. State Dirac’s sufficient condition (no proof).
  4. \(\chi(C_5)\) and \(\chi(K_4)\); why planar \(K_4\) needs 4 colors.
  5. Hall: give bipartite example with no matching saturating left side.
  6. Four color theorem: one-sentence statement.
  7. Planarity: why \(e\le 3v-6\) kills \(K_5\).

Section E — Modeling portfolio (25)

E1 (12 pts). Model one of the following fully (template + analysis):

    1. Package dependencies among 6 packages with at least one diamond dependency and a question about install order / cycle.
    1. Exam scheduling for 5 courses with a given conflict list; find \(\chi\) or bound it.
    1. Job–machine bipartite assignment with Hall check.

E2 (8 pts). Shortest-path or MST modeling in one paragraph + tiny numeric instance you invent (≤5 vertices).

E3 (5 pts). In one short paragraph: contrast Euler vs Hamilton on a street-vs-city tour for a municipal robot.

Answer key (self-mark)

8. Sum 14 ⇒ 7 edges; two odds; yes graphic (e.g. nearly regular).
9. Handshaking ⇒ sum even ⇒ even # odds.
10. Yes: tree would need 8 edges; 9 edges ⇒ cycle.
11. \(|E|=n-c=11\).
12. diam \(C_6=3\).
13. Tree ⇔ unique path between any pair.
14. Each arc contributes 1 to exactly one in and one out sum.
15. Order \(S,A,B,C,T\); \(d\): S0 A1 B1 C2 T2; parents \(A,B\leftarrow S\), \(C\leftarrow A\), \(T\leftarrow B\) (alpha). Levels: {S},{A,B},{C,T}.
16. Depends on alpha DFS—e.g. \(S,A,B,C,T\) tree edges along deep path—accept consistent tables.
17. Has triangles \(SAB\), \(ABC\)—odd cycles—not bipartite.
18. Orient \(S\to A,S\to B,A\to B,A\to C,B\to C,B\to T,C\to T\): DAG; topo e.g. \(S,A,B,C,T\).
19. \(d(T)=5\); path \(S{-}A{-}B{-}C{-}T\).
20. Start in-deg A0 B0 C2 D2; emit A,B then C then D; orders \(A,B,C,D\) or \(B,A,C,D\).
21. \(K_4\) all deg 3: no Euler circuit; 4 odds: no Euler trail.
22. No Hamilton cycle (unequal parts); yes Hamilton path.
23. \(n\ge 3\), \(\deg\ge n/2\) all \(v\) ⇒ Hamilton cycle.
24. \(\chi(C_5)=3\); \(\chi(K_4)=4\); clique of size 4.
25. e.g. three left vertices only into two right vertices.
26. Every planar graph is 4-colorable.
27. \(K_5\): \(n=5,m=10>9=3\cdot5-6\).
E1–E3. Grade by template completeness and correctness of analysis.

Remediation map

Weak Rework
A defs Days 59–60
B structure 59–61
C algorithms 62–64
D advanced 65–67
E modeling 68–69

Required skills checklist (Gate VI mandate)

  • At least one full model (E1)
  • Handshaking used correctly (B)
  • Tree edge-count / cycle check (B10–11 or 13)
  • BFS levels table (C15)
  • DAG topo or Kahn (C18 or C20)
  • Bipartite and/or matching (C17 or D25 or E1-iii)
  • Dijkstra numbers on tiny weighted graph (C19)

Portfolio reflection (after scoring)

Write 5–10 lines:

  1. Strongest graph skill?
  2. Weakest?
  3. Modeling mistake you nearly made?
  4. Ready for number theory / crypto stage?

Checkpoint

  • Full exam closed book
  • Score ≥ 75 with no section < 50%
  • All mandate checklist boxes ticked
  • Misses redone cold within 48h
  • Three model writeups saved from Day 69 + Gate
  • Reflection written

Two personal takeaways:

  1. …
  2. …

Deepening notes

Closed-book sketch sheet (write blank)

  • Handshaking; tree \(|E|=n-1\)
  • BFS dist table; Dijkstra table
  • Kahn in-degrees
  • Hall one line; Euler degrees; Dirac one line
  • \(\chi\ge\omega\); four color; \(m\le 3n-6\)
  • Modeling template headers

Full BFS answer (G1) reference

Discovery: \(S,A,B,C,T\).
\(d(S)=0,d(A)=d(B)=1,d(C)=d(T)=2\).
Parents: \(A\leftarrow S,B\leftarrow S,C\leftarrow A,T\leftarrow B\) (alpha).
Levels: \(L_0=\{S\},L_1=\{A,B\},L_2=\{C,T\}\).

Full Dijkstra reference

After processing \(S,A,B,C,T\): \(d=(0,2,3,4,5)\); path \(S{-}A{-}B{-}C{-}T\).

Extra gate items for rematch

R1. Havel–Hakimi \((3,3,2,2,2)\).
R2. Spanning trees of \(C_5\).
R3. Hall fail with \(|L|=4\).
R4. Critical path 5 tasks.
R5. \(\chi\) of conflict \(C_5\).
R6. Euler trail construction two odds.
R7. Model git merge DAG topo.
R8. Negative Dijkstra counterexample table.

48h remediation

Score band Action
≥75 Light review Stage VII prep
60–74 Redo weak section + 5 drills
<60 Rework Days 59–69 summaries

Stage VI exit criteria

  • Gate ≥75, no section <50%
  • Mandate checklist complete
  • Model template fluent
  • Dijkstra + BFS tables cold
  • Euler vs Hamilton one-liner
  • Tree characterizations listed

Extended practice battery (rematch)

Battery 1 — Structure

  1. Degrees \(5,3,3,3,2,2\): edges? Possible?
  2. Prove handshaking in two sentences.
  3. \(n=10\), connected, \(|E|=10\): cycle?
  4. Forest \(n=14\), \(|E|=10\): components?
  5. Diameter of \(P_7\) and \(K_{1,6}\).

Battery 2 — Algorithms

  1. BFS table on a path of 6 vertices from an end.
  2. DFS disc/fin on a binary tree shape (3 levels).
  3. Kahn on \(W\to X,W\to Y,X\to Z,Y\to Z\).
  4. Dijkstra: triangle \(s,a,t\) weights \(sa=4,st=9,at=3\)—dist \(s\) to \(t\).
  5. Negative counterexample: one-paragraph table.

Battery 3 — Advanced + modeling

  1. Euler status of \(K_{3,3}\).
  2. Hamilton path in \(K_{2,4}\)?
  3. Hall: \(L\) size 3 all to same 2 in \(R\)—violating \(S\).
  4. \(\chi(C_6)\), \(\chi(K_5)\).
  5. Model: “install plugins with depends” template.
  6. Model: “min latency route with weights” template.
  7. Euler vs Hamilton for museum corridor robot.
  8. Tree check: unique path on a graph you draw.
  9. Spanning trees of \(C_7\).
  10. Four color statement + one planar \(\chi=4\) example.

Partial solutions

  1. Sum 18 ⇒ 9 edges; two odds—OK possible.
  2. Yes cycle (\(|E|\ge n\)).
  3. \(c=n-|E|=4\).
  4. \(6\); \(2\).
  5. Path \(s{-}a{-}t\) weight \(7\).
  6. Deg 3,3,3,3,3,3—all odd: six odds—no Euler trail.
  7. Yes (start in size 4).
  8. \(S=L\).
  9. \(2\); \(5\).
  10. \(7\).

Confidence map

Topic Color
Handshaking / degrees
Paths / connectivity
Trees / Cayley / MST idea
BFS / DFS
DAG / topo / critical path
Dijkstra / BF
Bipartite / matching / Hall
Euler / Hamilton
Color / planar
CS modeling

Final Stage VI portfolio contents

  1. Gate exam with scores
  2. Three model writeups (Day 69 + E1)
  3. One Dijkstra table
  4. One BFS table
  5. One Kahn trace
  6. One Hall success + fail
  7. Confidence map

Archive before Stage VII (number theory / crypto).

Remediation map (Stage VI)

Weak area Return to
Degrees / handshaking / HH Day 59
Walks / connectivity / bridges Day 60
Trees / Cayley / MST idea Day 61
BFS / DFS Day 62
DAG / topo / critical path Day 63
Dijkstra / BF Day 64
Bipartite / Hall / matching Day 65
Euler / Hamilton Day 66
Coloring / planar awareness Day 67
CS modeling catalog Day 68
Modeling writeups Day 69

Gate VI self-score rubric

Criterion Weight
Correct graph model (\(V\), \(E\), directed/weight) High
Correct algorithm/theorem named High
Simulation table accuracy (BFS/Dijkstra/Kahn) High
Proof sketch (handshaking, tree TFAE, Hall setup) Medium
Complexity awareness (poly vs hard) Medium

Post-gate checklist

  • Scored each problem
  • Confidence map shaded
  • Yellow/red topics: 2 reworked problems each
  • Portfolio artifacts listed above complete
  • One-page Stage VI formula/algorithm sheet from memory

Synthesis

Stage VI built graphs from degrees through paths, trees, search, DAGs, shortest paths, bipartite structure, Euler/Hamilton, coloring, and CS modeling. Gate VI tests definitions + simulations + model choice. Stage VII leaves graphs for number theory: divisibility, modular arithmetic, and crypto culture—counting and graphs remain tools, not the main track.

Tomorrow

Day 71 — Divisibility: primes, gcd culture shift into Stage VII number theory foundations.