diff --git a/writeup.md b/writeup.md
index 63ea42f..1bb1d75 100644
--- a/writeup.md
+++ b/writeup.md
@@ -1,9 +1,381 @@
-# COMP182 Homework 3
+# COMP182 Homework 3: Graphs
 
 ## Student Responses
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+---
 
-[Your solutions here]
+## Problem 1: Understanding Graph-theoretic Definitions and Terminology
 
+### 1.1 Degree Sequences
+
+The degree sequence is listed in non-increasing order.
+
+**K_4 (complete graph on 4 nodes):**
+Every node is adjacent to every other node, so each node has degree 3.
+Degree sequence: **(3, 3, 3, 3)**
+
+**C_5 (cycle graph on 5 nodes):**
+Every node has exactly two neighbors (the node before and after it in the cycle), so each node has degree 2.
+Degree sequence: **(2, 2, 2, 2, 2)**
+
+**K_{m,n} (complete bipartite graph):**
+The first partition has m nodes, each adjacent to all n nodes in the second partition, so each has degree n. The second partition has n nodes, each adjacent to all m nodes in the first partition, so each has degree m.
+
+In non-increasing order (assuming m ≥ n without loss of generality):
+Degree sequence: **(m, m, ..., m, n, n, ..., n)** where m appears n times and n appears m times.
+
+(If m < n, simply swap: n appears m times followed by m appearing n times.)
+
+---
+
+### 1.2 Planar Graphs
+
+**K_2:** Planar. It is simply two nodes connected by a single edge — trivially drawn without crossings.
+
+```
+A --- B
+```
+
+**K_3:** Planar. It is a triangle — three nodes with three edges forming a cycle.
+
+```
+    A
+   / \
+  B---C
+```
+
+**K_4:** Planar. It can be drawn as a triangle with the fourth node placed inside, connected to all three outer nodes.
+
+```
+      A
+     / \
+    /   \
+   B--D--C
+    \   /
+     \ /
+      (B---C edge at bottom)
+```
+
+More precisely: place A, B, C as a triangle, and D inside it. The edges {A,B}, {A,C}, {B,C} are the triangle sides, and edges {A,D}, {B,D}, {C,D} go from the interior point to the triangle vertices. No edges cross.
+
+**K_5:** **Not planar.** By Euler's formula for planar graphs, a simple planar graph must satisfy E ≤ 3V − 6. For K_5: V = 5, E = 10, and 3(5) − 6 = 9. Since 10 > 9, K_5 cannot be planar.
+
+**Answer:** K_2, K_3, and K_4 are planar. K_5 is not planar.
+
+---
+
+### 1.3 Course Prerequisites
+
+**(a) Precedence Graph:**
+
+Nodes: COMP 140, MATH 111, MATH 211, ELEC 220, MATH 112, COMP 182, COMP 215, COMP 310, STAT 310, COMP 311, COMP 382, COMP 321, COMP 410
+
+Directed edges (prerequisite → course):
+
+```
+MATH 111 → MATH 112
+COMP 140 → COMP 182
+MATH 211 → COMP 182
+COMP 182 → COMP 215
+COMP 215 → COMP 310
+MATH 112 → STAT 310
+MATH 211 → STAT 310
+COMP 182 → COMP 311
+COMP 182 → COMP 382
+STAT 310 → COMP 382
+ELEC 220 → COMP 321
+COMP 215 → COMP 321
+COMP 321 → COMP 410
+COMP 310 → COMP 410
+COMP 311 → COMP 410
+```
+
+ASCII diagram (arrows point downward/right indicating prerequisite → course):
+
+```
+COMP 140    MATH 111    MATH 211    ELEC 220
+   \           |          / |           |
+    \          v         /  |           |
+     \     MATH 112    /   |           |
+      \        \      /    |           |
+       v        v    v     |           |
+      COMP 182  STAT 310   |           |
+      / |  \       |       |           |
+     /  |   \      |       |           |
+    v   v    v     v       |           |
+COMP 215 COMP311 COMP382   |           |
+   / \     |               |           |
+  v   v    |               |           |
+COMP310  COMP321 <---------+-----------+
+   \       |
+    v      v
+     COMP 410
+```
+
+**(b) Is the graph acyclic?**
+
+Yes, the graph is acyclic (it is a DAG — Directed Acyclic Graph). It would **not** make sense for it to be cyclic, because a cycle would mean that a course is (directly or indirectly) a prerequisite of itself. For example, if A requires B requires C requires A, then no student could ever take any of these courses, since each requires one of the others to be completed first. A cyclic prerequisite structure is logically impossible.
+
+**(c) Minimum number of semesters:**
+
+We perform topological level assignment — each course gets assigned to the earliest possible semester:
+
+- **Semester 1:** COMP 140, MATH 111, MATH 211, ELEC 220 (no prerequisites)
+- **Semester 2:** MATH 112 (needs MATH 111), COMP 182 (needs COMP 140 and MATH 211)
+- **Semester 3:** COMP 215 (needs COMP 182), COMP 311 (needs COMP 182), STAT 310 (needs MATH 112 and MATH 211)
+- **Semester 4:** COMP 310 (needs COMP 215), COMP 321 (needs ELEC 220 and COMP 215), COMP 382 (needs COMP 182 and STAT 310)
+- **Semester 5:** COMP 410 (needs COMP 321, COMP 310, and COMP 311)
+
+**The minimum number of semesters is 5.**
+
+**General method:** For an arbitrary prerequisite DAG, compute the minimum number of semesters as the length of the longest path plus 1. This can be done by:
+1. Perform a topological sort of the DAG.
+2. For each node v in topological order, compute level(v) = max(level(u) + 1) over all prerequisites u of v, with level(v) = 1 if v has no prerequisites.
+3. The minimum number of semesters is max over all nodes v of level(v).
+
+This runs in O(V + E) time using BFS-based topological ordering (Kahn's algorithm).
+
+---
+
+### 1.4 Matchings
+
+**(a) A graph with at least 5 nodes that has a matching of size 2:**
+
+Consider a graph G with nodes {1, 2, 3, 4, 5} and edges {1,2}, {3,4}, {4,5}.
+
+The matching M = {{1,2}, {3,4}} has size 2 (no two edges share a node).
+
+```
+1 --- 2     3 --- 4 --- 5
+```
+
+**(b) A graph with at least 5 nodes that has no matching of size 2:**
+
+Consider the star graph with center node 1 and leaves {2, 3, 4, 5}: edges are {1,2}, {1,3}, {1,4}, {1,5}.
+
+```
+  2
+  |
+  1 --- 3
+ / \
+4   5
+```
+
+Every edge is incident to node 1, so any two edges share node 1 in common. Therefore, no matching can contain more than one edge, and there is no matching of size 2.
+
+**(c) Size of a perfect matching:**
+
+In a perfect matching, every node is incident to exactly one edge in the matching. Each edge covers exactly 2 nodes. Since all n nodes must be covered, the number of edges in a perfect matching is **n/2**.
+
+---
+
+## Problem 2: Graph-theoretic Problem Formulation
+
+### 2.1 Jury Selection
+
+**Graph formulation:**
+- **Input:** A graph G = (V, E) where V is the set of n individuals in the city, and {u, v} ∈ E if and only if individuals u and v know each other. Also given is a positive integer m.
+- **Output:** An independent set S ⊆ V of size m — that is, a subset S with |S| = m such that for every pair u, v ∈ S, the edge {u, v} ∉ E (no two selected jurors know each other).
+
+This is the **Independent Set** problem: find an independent set of size m in G.
+
+---
+
+### 2.2 Student Groups
+
+**Graph formulation:**
+- **Input:** A graph G = (V, E) where V is the set of students in COMP 182, and {u, v} ∈ E if and only if students u and v like each other.
+- **Output:** A partition of V into the minimum number of subsets (groups) V_1, V_2, ..., V_k such that each V_i is a clique in G (i.e., for every pair u, v ∈ V_i, the edge {u, v} ∈ E).
+
+This is the **Minimum Clique Cover** problem. Equivalently, it corresponds to finding the chromatic number of the complement graph: let G' be the complement of G (where {u,v} ∈ E' iff {u,v} ∉ E). Then a clique in G is an independent set in G', and a minimum clique cover of G is equivalent to a proper vertex coloring of G' using the minimum number of colors. So the minimum number of groups equals χ(G'), the chromatic number of the complement graph.
+
+---
+
+### 2.3 Course Scheduling
+
+**Graph formulation:**
+- **Input:** A graph G = (V, E) where V is the set of Fall 2023 CS courses, and {u, v} ∈ E if and only if courses u and v have at least one student in common. Also given is a positive integer k (the number of available time slots).
+- **Output:** A proper vertex coloring f : V → {1, 2, ..., k} using the minimum number of colors such that for every edge {u, v} ∈ E, f(u) ≠ f(v). Each color represents a distinct time slot, and the coloring ensures no two courses with a common student are scheduled at the same time.
+
+This is the **Graph Coloring** (chromatic number) problem: find the minimum number of colors needed for a proper vertex coloring of G.
+
+---
+
+## Problem 3: Proving Graph-theoretic Results
+
+### 3.1 Bipartite Bit Vector Graph
+
+**Theorem:** B_n is bipartite for all n ≥ 2.
+
+**Proof:**
+
+We partition the vertex set of B_n into two sets based on the parity of the number of 1-bits:
+
+- Let A = {bit vectors with an **even** number of 1s}
+- Let B = {bit vectors with an **odd** number of 1s}
+
+Clearly A and B partition the vertex set V of B_n (every bit vector has either an even or odd number of 1s), and both A and B are non-empty for n ≥ 2 (e.g., 00...0 ∈ A and 10...0 ∈ B).
+
+Now consider any edge {s, t} ∈ E(B_n). By definition, s and t differ in exactly one bit. If s has k ones, then t has either k + 1 or k − 1 ones (flipping a 0 to 1 adds one 1, and flipping a 1 to 0 removes one 1). In either case, the parity of the number of 1s changes: if s has an even number of 1s, then t has an odd number, and vice versa.
+
+Therefore, every edge connects a vertex in A to a vertex in B. This means B_n is bipartite with partition (A, B). ∎
+
+---
+
+### 3.2 Bridges and Even Degrees
+
+**Theorem:** If the degrees of all nodes in graph g = (V, E) are even, then g does not contain a bridge.
+
+**Proof (by contradiction):**
+
+Assume for contradiction that all nodes in g have even degree and that e = {u, v} is a bridge of g.
+
+Since e is a bridge, removing e from g produces a graph g' = (V, E \ {e}) that has more connected components than g. Specifically, the connected component of g containing u and v is split into two connected components in g': one component C_u containing u and one component C_v containing v.
+
+In g', the degree of u is deg_g(u) − 1, which is **odd** (since deg_g(u) is even). For every other vertex w ∈ C_u with w ≠ u, we have deg_{g'}(w) = deg_g(w), which is **even** (since w is not an endpoint of the removed edge e, and v ∉ C_u).
+
+Now consider the sum of degrees of all vertices in the subgraph induced by C_u in g':
+
+$$\sum_{w \in C_u} \deg_{g'}(w) = \underbrace{(\deg_g(u) - 1)}_{\text{odd}} + \sum_{\substack{w \in C_u \\ w \neq u}} \underbrace{\deg_g(w)}_{\text{even}}$$
+
+This sum equals an odd number plus a sum of even numbers, which is **odd**.
+
+However, by the Handshaking Lemma, the sum of degrees of all vertices in any graph equals twice the number of edges, which is always **even**. Since C_u forms a connected component of g' (and thus the edges within C_u are well-defined), this sum must be even.
+
+This is a contradiction. Therefore, g cannot contain a bridge. ∎
+
+---
+
+### 3.3 Edge Coloring and Hamiltonian Circuits
+
+**Theorem:** If the degree of each node in g is 3 and g has a Hamiltonian circuit, then there exists a 3-coloring of g's edges (i.e., a proper edge coloring using 3 colors).
+
+**Proof:**
+
+**Step 1: n must be even.**
+Since every node has degree 3, the sum of all degrees is 3n = 2|E|. For this to be an integer, 3n must be even, which requires n to be even.
+
+**Step 2: Identify the Hamiltonian circuit and remaining edges.**
+Let H = u_1, u_2, ..., u_n, u_1 be a Hamiltonian circuit of g. The circuit H contains exactly n edges: {u_1, u_2}, {u_2, u_3}, ..., {u_{n-1}, u_n}, {u_n, u_1}.
+
+Each vertex u_i has degree 3 in g and degree 2 in H (it is incident to edges {u_{i-1}, u_i} and {u_i, u_{i+1}} in the circuit, with indices modulo n). Therefore, each vertex is incident to exactly 3 − 2 = 1 edge that is **not** in H.
+
+Let M = E \ E(H) be the set of edges not in H. Since every vertex is incident to exactly one edge in M, the set M is a **perfect matching** of g.
+
+**Step 3: Construct the 3-edge-coloring.**
+
+Color the edges as follows:
+
+- **Edges of H:** Since n is even, the Hamiltonian circuit is an even cycle. Assign colors alternately around the cycle:
+  - f({u_i, u_{i+1}}) = 1 if i is odd
+  - f({u_i, u_{i+1}}) = 2 if i is even
+  (indices modulo n, with {u_n, u_1} being edge index n, which is even, getting color 2)
+
+  Since the cycle has even length, this alternating coloring is consistent — the first and last edges around the cycle receive different colors (color 1 and color 2 respectively).
+
+- **Edges of M:** Assign color 3 to every edge in M:
+  - f(e) = 3 for all e ∈ M
+
+**Step 4: Verify the coloring is proper.**
+
+We must show that no two edges sharing a common node receive the same color:
+
+1. **Two edges of H sharing a vertex:** At each vertex u_i, the two incident edges in H are {u_{i-1}, u_i} and {u_i, u_{i+1}}. By the alternating assignment, consecutive edges in the cycle receive different colors (one gets color 1, the other gets color 2). ✓
+
+2. **An edge of H and an edge of M sharing a vertex:** At vertex u_i, the two H-edges have colors 1 and 2, and the M-edge has color 3. All three are distinct. ✓
+
+3. **Two edges of M sharing a vertex:** This cannot happen since M is a matching (no two edges in M share a vertex). ✓
+
+Therefore, f is a valid 3-coloring of g's edges. ∎
+
+---
+
+### 3.4 Cartesian Product Graphs
+
+Given connected graphs g_1 = (V_1, E_1) and g_2 = (V_2, E_2), the Cartesian Product graph is C = (V_C, E_C) where:
+- V_C = V_1 × V_2
+- E_C = {{(u, x), (v, y)} : {u, v} ∈ E_1 OR {x, y} ∈ E_2}
+
+Let |V_1| = m and |V_2| = n.
+
+#### (a) Hamiltonian circuits: PROVE (True)
+
+**Theorem:** If g_1 and g_2 both contain Hamiltonian circuits, then C contains a Hamiltonian circuit.
+
+**Proof (constructive):**
+
+Let H_1 = u_1, u_2, ..., u_m, u_1 be a Hamiltonian circuit in g_1, and H_2 = v_1, v_2, ..., v_n, v_1 be a Hamiltonian circuit in g_2.
+
+We construct a Hamiltonian circuit in C using a "snake" (boustrophedon) traversal:
+
+**Construction:** Visit the m × n vertices of C row by row, snaking through columns:
+
+- **Row u_1 (forward):** (u_1, v_1) → (u_1, v_2) → ... → (u_1, v_n)
+- **Transition:** (u_1, v_n) → (u_2, v_n)
+- **Row u_2 (backward):** (u_2, v_n) → (u_2, v_{n-1}) → ... → (u_2, v_1)
+- **Transition:** (u_2, v_1) → (u_3, v_1)
+- **Row u_3 (forward):** (u_3, v_1) → (u_3, v_2) → ... → (u_3, v_n)
+- ...continue alternating direction...
+- **Last row u_m:** traversed in the appropriate direction, ending at either (u_m, v_n) or (u_m, v_1)
+- **Return:** (u_m, v_?) → (u_1, v_1)
+
+**Verification that all edges exist in E_C:**
+
+1. **Within-row edges** (e.g., {(u_i, v_j), (u_i, v_{j+1})}): Since {v_j, v_{j+1}} ∈ E_2 (consecutive vertices in the Hamiltonian circuit H_2), this edge is in E_C. ✓
+
+2. **Row-to-row transitions** (e.g., {(u_i, v_?), (u_{i+1}, v_?)}): Since {u_i, u_{i+1}} ∈ E_1 (consecutive vertices in the Hamiltonian circuit H_1), this edge is in E_C regardless of the second coordinates. ✓
+
+3. **Return edge** ({(u_m, v_?), (u_1, v_1)}): Since {u_m, u_1} ∈ E_1 (the closing edge of H_1), this edge is in E_C regardless of the second coordinates. ✓
+
+**Verification that all vertices are visited exactly once:**
+
+The traversal visits all m rows (u_1 through u_m), and within each row, all n columns (v_1 through v_n). Each vertex (u_i, v_j) is visited exactly once. The total number of vertices visited is m × n = |V_C|. ✓
+
+Therefore, the constructed path visits every vertex exactly once and returns to the starting vertex, forming a Hamiltonian circuit in C. ∎
+
+---
+
+#### (b) Euler circuits: PROVE (True)
+
+**Theorem:** If g_1 and g_2 both contain Euler circuits, then C contains an Euler circuit.
+
+**Proof:**
+
+By Theorem 1 (Section 10.5), a connected graph has an Euler circuit if and only if every vertex has even degree. We show that C satisfies both conditions.
+
+**Step 1: C is connected.**
+
+Take any two vertices (u, x) and (u', x') in C. Since g_1 is connected, there exists a path u = w_0, w_1, ..., w_k = u' in g_1. Since {w_i, w_{i+1}} ∈ E_1 for each i, the edge {(w_i, x), (w_{i+1}, x)} ∈ E_C. So there is a path from (u, x) to (u', x) in C.
+
+Similarly, since g_2 is connected, there exists a path from x to x' in g_2, which gives a path from (u', x) to (u', x') in C.
+
+Combining these paths, (u, x) is connected to (u', x') in C. Since this holds for arbitrary vertices, C is connected. ✓
+
+**Step 2: Every vertex in C has even degree.**
+
+We compute the degree of vertex (u, x) in C. Vertex (u, x) is adjacent to (v, y) whenever {u, v} ∈ E_1 or {x, y} ∈ E_2 (these conditions ensure (u,x) ≠ (v,y) since there are no self-loops in g_1 or g_2).
+
+By inclusion-exclusion, the set of neighbors of (u, x) is:
+
+- A = {(v, y) : {u, v} ∈ E_1, y ∈ V_2} with |A| = deg_{g_1}(u) · n
+- B = {(v, y) : v ∈ V_1, {x, y} ∈ E_2} with |B| = m · deg_{g_2}(x)
+- A ∩ B = {(v, y) : {u, v} ∈ E_1, {x, y} ∈ E_2} with |A ∩ B| = deg_{g_1}(u) · deg_{g_2}(x)
+
+Therefore:
+
+deg_C(u, x) = deg_{g_1}(u) · n + m · deg_{g_2}(x) − deg_{g_1}(u) · deg_{g_2}(x)
+
+Since g_1 has an Euler circuit, all degrees in g_1 are even: deg_{g_1}(u) is even for all u.
+Since g_2 has an Euler circuit, all degrees in g_2 are even: deg_{g_2}(x) is even for all x.
+
+Let d_1 = deg_{g_1}(u) (even) and d_2 = deg_{g_2}(x) (even). Then:
+
+deg_C(u, x) = d_1 · n + m · d_2 − d_1 · d_2
+
+- d_1 · n is even (since d_1 is even)
+- m · d_2 is even (since d_2 is even)
+- d_1 · d_2 is even (since both are even)
+
+Therefore deg_C(u, x) = even + even − even = **even**. ✓
+
+**Conclusion:** Since C is connected and every vertex of C has even degree, by Theorem 1 (Section 10.5), C contains an Euler circuit. ∎