Day 70 — Gate VI

Updated

July 30, 2026

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.