Week-12

Maths 1: Week 12 - The Master Encyclopedia of Advanced Systems

1. The Genesis: The 3D Constraint 📜

1.1 The Mapmakers Dilemma

In the 1850s, a graduate student named Francis Guthrie noticed that he could color a map of the counties of England using only four colors, such that no two adjacent counties shared a color. This “Four Color Theorem” became one of the most famous problems in math. It represents Graph Coloring—how we partition resources without conflict.

1.2 The Expansion into Surfaces

For 11 weeks, we have worked on the floor ($X$-axis and $Y$-axis). But the world is not a flat drawing. It is a surface of peaks and valleys. In the final half of this course, we introduce Multivariable Calculus. This is the math that allows us to model a mountain range, a weather system, or the way a virus spreads across a population. We stop looking at “The Speed” of a point and start looking at “The Slope” of a Surface.

---

2. Advanced Graph Theory: Planarity & Space 🏛️

2.1 Planality (The Flatness Rule)

A graph is Planar if it can be drawn on a piece of paper without any edges crossing.

• Euler’s Formula: For a connected planar graph: $V-E+F=2$ (Vertices - Edges + Faces = 2). Note: The “Faces” include the single, infinite outside area.

2.2 The Non-Planar Kings

Not every graph can be flat. There are two “Minimum” non-planar graphs:

1. $K_5$: Five points, everyone connected. (Crossing is required).
2. $K_{3,3}$: Six points in two piles of 3. (You can’t connect all of them without crossing).

• Kuratoskis Theorem: A graph is non-planar if it contains either $K_5$ or $K_{3,3}$ hidden inside it.

---

3. The Topology of Color: Chromatic Numbers 🛠️

3.1 Vertex Coloring

Assigning colors (integers) to vertices such that neighbors have Different Colors.

• Chromatic Number $\chi (G)$: The smallest number of colors needed.
• Laws of Coloring:
  1. $\chi (K_n)=n$ (Everyone is connected, so everyone needs their own color).
  2. $\chi (\text{Bipartite})=2$ (By definition!).
  3. $\chi (\text{Cycle})$:
     • 2 if cycle is Even.
     • 3 if cycle is Odd.

---

4. Multivariable Calculus: The Higher Dimensions 🖋️

4.1 Functions of Two Variables $f(x,y)$

Instead of a curve, we have a Surface $z=f(x,y)$.

• Domain: A region in the $XY$-plane.
• Range: A range of heights on the $Z$-axis.

4.2 Partial Derivatives (The Directional Speeds)

If you are on a coordinate at $(x,y)$ and you want to know how steep the ground is:

1. $f_x$ (Partial w.r.t $x$): Walk only East/West. Treat $y$ as a constant number (like 5).
2. $f_y$ (Partial w.r.t $y$): Walk only North/South. Treat $x$ as a constant number.

4.3 The Critical Points of a Surface

To find the peaks and valleys on a 3D surface, we need BOTH $f_x=0$ and $f_y=0$.

• The Saddle Point: A point that is a Maximum in one direction but a Minimum in another. (It looks like a mountain pass or a pringles chip!).

---

5. Optimization: Second Derivative Test (D-Test) 📈

5.1 The Discriminant of a Surface

To tell if a critical point is a Max, Min, or Saddle, we calculate $D$: $D=f_{xx}{f}_{yy}-(f_{xy}{)}^2$

1. $D>0$ and $f_{xx}>0$: Local MIN.
2. $D>0$ and $f_{xx}<0$: Local MAX.
3. $D<0$: Saddle Point.
4. $D=0$: The test is inconclusive.

---

6. The Encyclopedia of Worked Examples (10 Case Studies) 📚

Case 1: Using Euler’s Formula

Problem: A planar graph has 10 vertices and 15 edges. How many faces?

• Step 1: $V-E+F=2$.
• Calculation: $10-15+F=2$.
• Result: $F=2+5=7$ faces.

Case 2: Proving $K_{3,3}$ is Non-Planar

Problem: For a planar bipartite graph, $E\le 2V-4$. Test for $K_{3,3}$.

• Step 1: $|V|=6,|E|=9$.
• Calculation: $9\le 2(6)-4⟹9\le 8$.
• Result: Inequality fails. $K_{3,3}$ is Non-Planar.

Case 3: Finding Chromatic Number of a Star Graph

Problem: $\chi (G)$ for a star graph with 10 neighbors?

• Logic: Star graphs are bipartite (center is one set, neighbors are the other).
• Result: 2.

Case 4: Coloring a Wheel Graph ($W_n$)

Problem: Find $\chi (W_6)$. (A 6-vertex cycle with a center node connected to all).

• Logic: The outer cycle has 5 nodes (Odd). Needs 3 colors. The center node is connected to all of them. Needs a 4th color.
• Result: 4.

Case 5: Calculating Partial Derivative ($f_x$)

Problem: $f(x,y)=x^3+x^2{y}^3-5y^2$. Find $f_x$.

• Logic: Treat $y$ as a constant.
• Calculation: $3x^2+2x{y}^3-0$.
• Result: $3x^2+2x{y}^3$.

Case 6: Calculating Partial Derivative ($f_y$)

Problem: Using Case 5, find $f_y$.

• Calculation: $0+3x^2{y}^2-10y$.
• Result: $3x^2{y}^2-10y$.

Case 7: Mixed Partials (Clairauts Theorem)

Problem: Prove $f_{xy}=f_{yx}$ for $f(x,y)=x{y}^2$.

• **$f_x=y^2⟹f_{xy}=2y$.
• **$f_y=2xy⟹f_{yx}=2y$.
• Result: They are equal!

Case 8: Finding Critical Points on a Surface

Problem: $f(x,y)=x^2+y^2$. Find the critical point.

• **$f_x=2x=0⟹x=0$.
• **$f_y=2y=0⟹y=0$.
• Result: Critical point at $(0,0)$. (This is the bottom of a 3D bowl).

Case 9: Testing for a Saddle Point

Problem: $f(x,y)=x^2-y^2$. Is $(0,0)$ a saddle?

• **$f_{xx}=2,f_{yy}=-2,f_{xy}=0$.
• Calculation: $D=(2)(-2)-0=-4$.
• Result: $D<0$, so yes, it is a Saddle Point.

Case 10: The Four-Color Application

Problem: If you have a graph representing adjacency of four states (A-B-C-D forming a circle), how many colors are needed?

• Logic: It’s an even cycle.
• Result: 2 colors.

---

7. Fundamental “How-To” Recipes 🍳

Recipe: Finding Peaks and Valleys on Surfaces

1. Partials: Calculate $f_x$ and $f_y$.
2. Roots: Solve the system $\{f_x=0,f_y=0\}$. These $(x,y)$ are your candidates.
3. D-Test: Calculate $f_{xx},f_{yy},f_{xy}$. Find $D$.
4. Verdict: Use the D-Test table to crown your Winner.

Recipe: Checking if a Graph is Bipartite (Red-Blue coloring)

1. Pick any node: Color it Blue.
2. Breadth-First: Color all its direct neighbors Red.
3. Check neighbors: Color neighbors of Red nodes Blue.
4. Conflict: If a node and its neighbor both end up Red or both Blue, the graph is NOT bipartite.

---

8. Encyclopedia Mastery Challenge 🏆

1. The Euler Bound: Prove that for any simple planar graph, $E\le 3V-6$.
2. The 3D Gradient: Imagine you are a ball rolling down $f(x,y)=x^2+y^2$. In which direction is the “Steepest Ascent”? (Hint: Research the Gradient $\nabla f$).
3. Kuratoskis Challenge: Draw a graph with 6 vertices that is non-planar but doesn’t have a triangle. (Hint: $K_{3,3}$).
4. The Final Surface: Prove that $f(x,y)=x^2+5y^2+10$ has a global minimum but NO global maximum.

---

🚀 The Journey Ends: You have completed the Master Encyclopedia of Maths 1. From the atomic sets of Week 1 to the complex surfaces of Week 12, you have mapped the logic of the universe.

Academic Champion Status: ACHIEVED. 🎓 助