diff --git a/writeup.md b/writeup.md
index 63ea42f..9a68b32 100644
--- a/writeup.md
+++ b/writeup.md
@@ -1,9 +1,390 @@
-# COMP182 Homework 3
+# COMP182 Homework 3: Graphs
 
-## Student Responses
+## Problem 1: Understanding Graph-theoretic Definitions and Terminology
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+### 1.1 Degree Sequences
 
-[Your solutions here]
+**K_4 (Complete Graph on 4 nodes):**
+In K_4, every node is connected to all other 3 nodes. Therefore, each node has degree 3.
+**Degree sequence: [3, 3, 3, 3]**
 
+**C_5 (Cycle on 5 nodes):**
+In a cycle, each node is connected to exactly 2 neighbors. Therefore, each node has degree 2.
+**Degree sequence: [2, 2, 2, 2, 2]**
+
+**K_{m,n} (Complete Bipartite Graph):**
+In the complete bipartite graph K_{m,n}, there are m nodes in one part and n nodes in the other part. Each node in the first part is connected to all n nodes in the second part (degree n), and each node in the second part is connected to all m nodes in the first part (degree m).
+**Degree sequence (in non-increasing order):**
+- If m ≥ n: [m, m, ..., m (n times), n, n, ..., n (m times)]
+- If n > m: [n, n, ..., n (m times), m, m, ..., m (n times)]
+- More generally: [max(m,n), max(m,n), ..., min(m,n), min(m,n), ...]
+
+---
+
+### 1.2 Planar Graphs
+
+**K_2** (2 nodes with 1 edge): **PLANAR**
+Drawing: A single line segment between two points.
+
+**K_3** (3 nodes with 3 edges - a triangle): **PLANAR**
+Drawing: A triangle with vertices at three points in the plane.
+
+**K_4** (4 nodes with 6 edges): **PLANAR**
+Drawing: Can be drawn as a square with a vertex in the middle connected to all four corners, or as a square with the diagonals drawn (the diagonals can be drawn slightly inside/outside to avoid intersection).
+
+**K_5** (5 nodes with 10 edges): **NOT PLANAR**
+Explanation: By Kuratowski's theorem, K_5 is one of the two fundamental non-planar graphs. K_5 requires more than 2 dimensions to draw without edge crossings. This can be proven by considering Euler's formula for planar graphs: for a connected planar graph, V - E + F = 2 where F is the number of faces. A planar graph has at most 3V - 6 edges. For K_5, we would need 10 ≤ 3(5) - 6 = 9, which is false. Therefore, K_5 cannot be planar.
+
+---
+
+### 1.3 Course Prerequisites
+
+**(a) Precedence Graph:**
+
+The precedence graph is a directed acyclic graph (DAG) where an edge from course A to course B indicates that B is a direct prerequisite for A (or equivalently, A depends on B).
+
+```
+Nodes (Courses):
+COMP 140, MATH 111, MATH 211, ELEC 220 (no prerequisites)
+MATH 112 (prerequisite: MATH 111)
+COMP 182 (prerequisites: COMP 140, MATH 211)
+COMP 215 (prerequisite: COMP 182)
+COMP 310 (prerequisite: COMP 215)
+STAT 310 (prerequisites: MATH 112, MATH 211)
+COMP 311 (prerequisite: COMP 182)
+COMP 382 (prerequisites: COMP 182, STAT 310)
+COMP 321 (prerequisites: ELEC 220, COMP 215)
+COMP 410 (prerequisites: COMP 321, COMP 310, COMP 311)
+
+Edges (Direct prerequisites only):
+MATH 111 → MATH 112
+MATH 111 → MATH 111 (starting point)
+MATH 211 → COMP 182
+MATH 211 → STAT 310
+COMP 140 → COMP 182
+COMP 182 → COMP 215
+COMP 182 → COMP 311
+COMP 182 → COMP 382
+COMP 215 → COMP 310
+COMP 215 → COMP 321
+ELEC 220 → COMP 321
+STAT 310 → COMP 382
+COMP 321 → COMP 410
+COMP 310 → COMP 410
+COMP 311 → COMP 410
+```
+
+**(b) Is the graph acyclic?**
+
+**Yes, the graph is acyclic (it is a DAG).**
+
+This makes sense because the prerequisite structure must be acyclic. A cycle in the prerequisite graph would mean that course A requires course B, B requires C, and eventually C requires A (directly or indirectly). This would create an impossible situation where a student cannot complete the required prerequisites. Real course prerequisite systems must be acyclic to be well-defined and implementable.
+
+**(c) Minimum number of semesters:**
+
+To find the minimum number of semesters, we compute the longest path in the DAG from a node with no prerequisites to a node with maximum dependency depth.
+
+**Topological levels:**
+- **Level 1 (Semester 1):** COMP 140, MATH 111, MATH 211, ELEC 220 (no prerequisites)
+- **Level 2 (Semester 2):** MATH 112 (needs MATH 111), COMP 182 (needs COMP 140, MATH 211)
+- **Level 3 (Semester 3):** COMP 215 (needs COMP 182), COMP 311 (needs COMP 182), STAT 310 (needs MATH 112, MATH 211)
+- **Level 4 (Semester 4):** COMP 321 (needs ELEC 220, COMP 215), COMP 310 (needs COMP 215), COMP 382 (needs COMP 182, STAT 310)
+- **Level 5 (Semester 5):** COMP 410 (needs COMP 321, COMP 310, COMP 311)
+
+**Minimum number of semesters: 5**
+
+**General algorithm for arbitrary precedence graphs:**
+For an arbitrary precedence graph (DAG) representing course prerequisites:
+1. Perform a topological sort of the graph
+2. Compute the longest path length in the DAG from any source node (course with no prerequisites) to any sink node
+3. The minimum number of semesters equals the length of the longest path (counting nodes, not edges) or equivalently, the maximum topological level
+4. Alternatively, use a dynamic programming approach: for each node, compute its level as 1 + max(levels of all prerequisite courses), with base case level = 1 for nodes with no prerequisites
+
+---
+
+### 1.4 Matchings
+
+**(a) Example of a graph with at least 5 nodes and a matching of size 2:**
+
+Consider a path graph with 5 nodes: 1 - 2 - 3 - 4 - 5
+
+A matching of size 2 could be: {(1,2), (3,4)}
+
+Another example is a star graph with 5 nodes (one central node connected to 4 leaves). A matching of size 2 could be any two edges that don't share a common vertex: {(center, leaf1), (center, leaf2)} - Wait, this doesn't work because both edges share the center. Let me reconsider: in a star with 5 nodes (1 center and 4 leaves), a matching of size 2 would be two edges from different leaves to the center... but that violates the matching condition. Actually, in a star graph, a matching can have at most size 1 because all edges share the central node.
+
+Better example: A cycle of 5 nodes: 1 - 2 - 3 - 4 - 5 - 1
+
+A matching of size 2: {(1,2), (3,4)} ✓
+
+**(b) Example of a graph with at least 5 nodes and no matching of size 2:**
+
+Consider a star graph K_{1,4} with one central node c and 4 leaves {1, 2, 3, 4}:
+
+Edges: {(c,1), (c,2), (c,3), (c,4)}
+
+Any matching can include at most 1 edge because all edges share the central vertex c. Therefore, this graph has no matching of size 2. ✓
+
+**(c) Size of a perfect matching for a graph with n nodes (n even):**
+
+A perfect matching is a matching where every node is incident with at least one edge. For a graph with n nodes (where n is even), each edge in a matching covers exactly 2 nodes.
+
+If every node must be incident with at least one edge in the matching, and we want to cover all n nodes with non-overlapping edges, we need exactly n/2 edges.
+
+**The size of a perfect matching (if one exists) for a graph with n nodes (n even) is n/2.** ✓
+
+---
+
+## Problem 2: Graph-theoretic Problem Formulation
+
+### 2.1 Jury Selection
+
+**Problem Formulation:**
+
+**Input:**
+- A graph G = (V, E) where:
+  - V = {individuals in the city} with |V| = n
+  - E = {(u, v) : individuals u and v know each other}
+- An integer m (the size of jury to select)
+
+**Output:**
+- A subset S ⊆ V with |S| = m such that for any two distinct nodes u, v ∈ S, there is no edge between u and v in G (i.e., no two people in the jury know each other)
+
+**Graph Problem:** Find an **independent set of size m** in G.
+
+The goal is to select m people such that no two of them know each other, which corresponds to finding an independent set (a set of vertices with no edges between them).
+
+---
+
+### 2.2 Student Groups
+
+**Problem Formulation:**
+
+**Input:**
+- A graph G = (V, E) where:
+  - V = {students in COMP 182}
+  - E = {(u, v) : students u and v like each other}
+
+**Output:**
+- A partition of V into the minimum number of disjoint subsets {G_1, G_2, ..., G_k} such that:
+  - Each G_i is a complete subgraph (clique) of G (every pair of students in the group likes each other)
+  - Every student belongs to exactly one group
+  - k is minimized
+
+**Graph Problem:** Find the **minimum clique cover** of G.
+
+Alternatively, this is equivalent to finding a **proper coloring of the complement graph G'** (where edges exist between students who don't like each other), which is the **chromatic number χ(G')**.
+
+---
+
+### 2.3 Course Scheduling
+
+**Problem Formulation:**
+
+**Input:**
+- A graph G = (V, E) where:
+  - V = {courses to be scheduled in Fall 2023}
+  - E = {(u, v) : courses u and v have at least one student in common}
+- An integer k (number of available time slots)
+
+**Output:**
+- A coloring function f: V → {1, 2, ..., k} such that:
+  - For any edge (u, v) ∈ E, f(u) ≠ f(v) (adjacent courses have different time slots)
+  - k is minimized (use as few time slots as possible)
+
+**Graph Problem:** Find a **proper k-coloring** of G, where k is the **chromatic number χ(G)** of the conflict graph.
+
+This ensures that courses with common students are scheduled in different time slots.
+
+---
+
+## Problem 3: Proving Graph-theoretic Results
+
+### 3.1 Bipartite Bit Vector Graph
+
+**Claim:** B_n is bipartite for any n ≥ 2.
+
+**Proof:**
+
+We partition the vertex set V into two disjoint sets based on the parity of the number of 1-bits in each bit vector:
+
+- **Set A:** All bit vectors with an **even** number of 1-bits
+- **Set B:** All bit vectors with an **odd** number of 1-bits
+
+**Observation:** Every bit vector belongs to either A or B (not both).
+
+**Key observation:** Two nodes (bit vectors) are connected by an edge in B_n if and only if they differ in exactly one bit.
+
+**Claim:** All neighbors of a node in A are in B, and vice versa.
+
+**Proof of claim:**
+- If a bit vector x ∈ A has an even number of 1-bits, and we flip exactly one bit to get y:
+  - If the flipped bit was 0, it becomes 1 (number of 1-bits increases by 1, becoming odd) → y ∈ B
+  - If the flipped bit was 1, it becomes 0 (number of 1-bits decreases by 1, becoming odd) → y ∈ B
+
+- If a bit vector x ∈ B has an odd number of 1-bits, and we flip exactly one bit to get y:
+  - If the flipped bit was 0, it becomes 1 (number of 1-bits increases by 1, becoming even) → y ∈ A
+  - If the flipped bit was 1, it becomes 0 (number of 1-bits decreases by 1, becoming even) → y ∈ A
+
+Therefore, every edge in B_n connects a node in A to a node in B, and no two nodes in A are adjacent, and no two nodes in B are adjacent.
+
+**Conclusion:** B_n is bipartite with partition (A, B). ✓
+
+---
+
+### 3.2 Bridges and Even Degrees
+
+**Claim:** If all vertices in a graph g = (V, E) have even degree, then g contains no bridge.
+
+**Proof:**
+
+A bridge is an edge whose removal increases the number of connected components.
+
+**Key Lemma:** A connected graph has an Eulerian circuit if and only if all vertices have even degree. (Euler's theorem)
+
+An Eulerian circuit is a circuit that traverses every edge exactly once.
+
+**Main Proof:**
+
+Suppose all vertices in g have even degree. Consider any edge e = {u, v} ∈ E.
+
+**Case 1:** g is connected.
+
+If g is connected and all vertices have even degree, then g has an Eulerian circuit C. This circuit C is a closed walk that traverses every edge exactly once.
+
+Since C is an Eulerian circuit, both u and v must appear in C. The path from u to v in C (along the circuit) uses only edges in E.
+
+Now consider the graph g' = (V, E \ {e}) (the graph with edge e removed).
+
+Since there is a path from u to v in the Eulerian circuit C that doesn't use the edge e (the path can go the "other way" around the circuit, using different edges), vertices u and v remain connected in g'.
+
+Therefore, removing edge e does not disconnect g, so e is not a bridge.
+
+**Case 2:** g is disconnected.
+
+A bridge is defined with respect to connected components. An edge e is a bridge if removing it increases the number of connected components. If e is within a connected component, the argument from Case 1 applies. If e is a cut-edge between components, we cannot have all vertices with even degree (the vertices on the boundary would need edges only to other components, making degree counting impossible in a consistent way), but more directly: removing a bridge would increase the number of components. If g is disconnected and all vertices have even degree, each connected component has all vertices with even degree, and the argument from Case 1 applies to each component.
+
+**Conclusion:** g contains no bridge. ✓
+
+---
+
+### 3.3 Edge Coloring and Hamiltonian Circuits
+
+**Claim:** If g = (V, E) has every vertex with degree 3 and contains a Hamiltonian circuit, then there exists a 3-coloring of the edges of g.
+
+**Proof:**
+
+Let H be a Hamiltonian circuit in g. The circuit H is a cycle that includes every vertex exactly once and uses 2 edges incident to each vertex.
+
+**Step 1: Color the edges in the Hamiltonian circuit.**
+
+The Hamiltonian circuit H is a cycle. For any cycle (even or odd), we can properly 2-edge-color it:
+- Assign color 1 to alternating edges in the cycle
+- Assign color 2 to the remaining edges in the cycle
+
+This ensures no two adjacent edges (edges sharing a vertex) in the cycle have the same color.
+
+**Verification:** In a cycle, at each vertex, one edge has color 1 and one edge has color 2, so they're different. ✓
+
+**Step 2: Color the remaining edges.**
+
+Since each vertex has degree 3 and the Hamiltonian circuit uses 2 edges per vertex, there is exactly 1 remaining edge incident to each vertex (not in H).
+
+Let F = E \ E(H) be the set of remaining edges. These edges form a 1-regular spanning subgraph of g (i.e., a perfect matching).
+
+**Key property of a matching:** No two edges in a matching share a vertex.
+
+**Step 3: Assign color 3 to all edges in F.**
+
+Since no two edges in the matching F share a vertex, we can safely assign color 3 to all of them without creating a conflict (two edges with the same color sharing a vertex).
+
+**Conclusion:** We have a 3-coloring of all edges: use colors {1, 2} for H (properly 2-colored) and color 3 for F. ✓
+
+---
+
+### 3.4 Cartesian Product Graphs
+
+**Definition:** The Cartesian product of two connected graphs g₁ = (V₁, E₁) and g₂ = (V₂, E₂) is C = (V_C, E_C) where:
+- V_C = V₁ × V₂
+- E_C = {{(u, x), (v, y)} : {u, v} ∈ E₁ OR {x, y} ∈ E₂}
+
+**Key observation about edges:** Two nodes (u, x) and (v, y) are adjacent in C if and only if:
+- u = v and {x, y} ∈ E₂ (edge in the g₂ direction), OR
+- x = y and {u, v} ∈ E₁ (edge in the g₁ direction)
+
+The degree of vertex (u, x) in C is: deg_C(u, x) = deg_{g₁}(u) + deg_{g₂}(x)
+
+---
+
+**Part (a): If g₁ and g₂ both contain Hamiltonian circuits, then C contains a Hamiltonian circuit.**
+
+**Claim: TRUE**
+
+**Proof:**
+
+Let H₁ = v₁, v₂, ..., v_m, v₁ be a Hamiltonian circuit in g₁ (visiting all m vertices)
+Let H₂ = x₁, x₂, ..., x_n, x₁ be a Hamiltonian circuit in g₂ (visiting all n vertices)
+
+We construct a Hamiltonian circuit in C using a "snake" pattern:
+
+**Construction:**
+1. Start at (v₁, x₁)
+2. Follow the H₂ path in the fiber {(v₁, y) : y ∈ V₂}:
+   - (v₁, x₁) → (v₁, x₂) → ... → (v₁, x_n)
+3. Move to the next fiber: (v₁, x_n) → (v₂, x_n) [using an edge from H₁]
+4. Follow H₂ in reverse in the {(v₂, y) : y ∈ V₂} fiber:
+   - (v₂, x_n) → (v₂, x_{n-1}) → ... → (v₂, x₁)
+5. Move to the next fiber: (v₂, x₁) → (v₃, x₁) [using an edge from H₁]
+6. Continue alternating: forward/reverse through each fiber, connected by edges from H₁
+7. After processing all m fibers, we return to (v₁, x₁)
+
+**Verification:**
+- We visit each (v_i, x_j) exactly once (all m × n vertices) ✓
+- Each step uses an edge in C (either within a fiber using H₂, or between fibers using H₁) ✓
+- We return to the starting vertex, forming a circuit ✓
+
+**Conclusion:** C contains a Hamiltonian circuit. ✓
+
+---
+
+**Part (b): If g₁ and g₂ both contain Euler circuits, then C contains an Euler circuit.**
+
+**Claim: TRUE**
+
+**Proof:**
+
+**Recall (Theorem 1 from Section 10.5):** A connected graph has an Euler circuit if and only if all vertices have even degree.
+
+**Given:** g₁ has an Euler circuit, so all vertices in g₁ have even degree.
+**Given:** g₂ has an Euler circuit, so all vertices in g₂ have even degree.
+
+**Claim:** All vertices in C have even degree.
+
+**Proof of claim:**
+- For any vertex (u, x) in C:
+  - deg_C(u, x) = deg_{g₁}(u) + deg_{g₂}(x)
+  - Since deg_{g₁}(u) is even and deg_{g₂}(x) is even:
+  - deg_C(u, x) = even + even = even ✓
+
+**Is C connected?**
+
+Both g₁ and g₂ are given as connected. For any two vertices (u, x) and (u', x') in C:
+- Use a path in g₁ from u to u' to move between fibers (staying in x-coordinate)
+- Use a path in g₂ from x to x' within the u'-fiber
+
+This shows C is connected. ✓
+
+**Conclusion:**
+
+By Theorem 1 (Euler's criterion):
+- C is connected ✓
+- All vertices in C have even degree ✓
+- Therefore, C has an Euler circuit ✓
+
+---
+
+## Summary
+
+All problems have been addressed:
+- **Problem 1:** Degree sequences, planarity, course prerequisites DAG analysis, and matching definitions
+- **Problem 2:** Formulations for jury selection (independent set), student groups (clique cover), and course scheduling (graph coloring)
+- **Problem 3:** Complete proofs for bipartite bit vectors, bridges and even degrees, edge coloring with Hamiltonian circuits, and Cartesian product properties