Week-10

Maths 1: Week 10 - The Master Encyclopedia of Network Topology

1. The Genesis: The Bridge Controversy 📜

1.1 Euler and the Seven Bridges of Königsberg

In 1736, the city of Königsberg in Prussia (now Russia) had seven bridges connecting two islands to the mainland. The citizens asked: “Is it possible to walk through the city and cross every bridge exactly once?”

The great Leonhard Euler realized that to solve this, the actual map, the distance between streets, and the size of the islands didn’t matter. All that mattered was Connectivity. He redrew the map as a series of dots (islands) and lines (bridges). This was the birth of Graph Theory (or Network Topology).

Euler proved it was impossible, essentially inventing the field of Discrete Mathematics that powers the internet, Google Maps, and Social Media today.

1.2 The Philosophical Intuition

A Graph is a model of Relationships. While calculus is about smooth, continuous change, Graph Theory is about “Atomic” connections. It is the math of “Who is connected to whom.”

---

2. Axiomatic Foundations: Defining the Network 🏛️

2.1 Formal Definition of a Graph

A Graph $G=(V,E)$ consists of:

1. Vertices ($V$): A non-empty set of points (nodes).
2. Edges ($E$): A set of pairs representing connections between vertices.

• Order of Graph: The number of vertices $|V|$.
• Size of Graph: The number of edges $|E|$.

2.2 The Handshaking Lemma (The Global Law)

Every edge has exactly two ends. Therefore, if you add up the number of connections (degree) at every vertex, you will always get exactly double the number of edges. ${\sum }_{v\in V}\text{deg}(v)=2|E|$

• The Corollary: In any network, the number of vertices with an Odd degree must be Even. (You can’t have an odd number of people each shaking an odd number of hands).

---

3. The Topology of Parts: Subgraphs & Paths 🛠️

3.1 Paths, Cycles, and Trails

1. Walk: Any sequence of vertices and edges.
2. Path: A walk where no vertex is visited twice.
3. Cycle: A path that starts and ends at the SAME vertex.
4. Complete Graph ($K_n$): A network where everyone is connected to everyone else. The number of edges in $K_n$ is $\frac{n(n-1)}{2}$.

3.2 Connectivity

A graph is Connected if you can get from any vertex to any other vertex using existing edges.

• If a graph is not connected, it is made of separate Components.

---

4. Bipartite Graphs: The Math of Matching 🖋️

4.1 The Two-Pile Axiom

A graph is Bipartite if you can split its vertices into two sets ($U$ and $W$) such that every edge connects a vertex in $U$ to one in $W$. Edges within the same set are forbidden.

• Mental Model: A graph of “Students” and “Classes.” Students only connect to classes, never to other students (in this model).
• The Cycle Rule: A graph is bipartite if and only if it has No Odd Cycles. (You can’t have a triangle in a bipartite graph).

---

5. Representing the Network: Matrices 📈

5.1 Adjacency Matrix ($A$)

A square matrix where the entry is $1$ if two vertices are connected and $0$ if they are not.

• The Power of the Matrix: If you multiply the adjacency matrix by itself ($A^2$), the resulting numbers tell you how many ways there are to get from point A to point B in exactly two steps.

---

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

Case 1: Finding Edges from Degrees

Problem: A graph has vertices with degrees $\{5,4,3,2,2\}$. Is this possible?

• Logic: Use the Handshaking Lemma. Sum of degrees $=5+4+3+2+2=16$.
• Calculation: $16/2=8$ edges.
• Result: Yes, because the sum is even.

Case 2: The Complete Graph Edge Count

Problem: How many edges are in $K_6$ (Everyone connected in a group of 6)?

• Formula: $n(n-1)/2⟹6(5)/2=15$.
• Result: 15 edges.

Case 3: Checking for Bipartiteness

Problem: Is a square ($V_1\to V_2\to V_3\to V_4\to V_1$) bipartite?

• Logic: Try to color vertices with 2 colors. $V_1$ (Red), $V_2$ (Blue), $V_3$ (Red), $V_4$ (Blue). No two neighbors have the same color.
• Result: Yes.

Case 4: The Triangle Failure

Problem: Is a triangle bipartite?

• Logic: Cycle of length 3 (Odd). Color test: $V_1$(R), $V_2$(B), $V_3$ MUST be Red, but $V_3$ is a neighbor of $V_1$. Conflict!
• Result: No.

Case 5: Finding Components

Problem: A graph with 6 vertices has edges $(1,2),(2,3),(4,5),(5,6)$. How many components?

• Analysis: $\{1,2,3\}$ are connected. $\{4,5,6\}$ are connected. They don’t touch each other.
• Result: 2 Components.

Case 6: The Degree of a Regular Graph

Problem: A 3-regular graph has 10 vertices. How many edges?

• Think: “3-regular” means every vertex has degree 3.
• Calculation: Sum $=10\times 3=30$. Edges $=30/2=15$.
• Result: 15.

Case 7: Path Length

Problem: What is the length of the path $2\to 3\to 5\to 8$?

• Logic: Length is the number of Edges, not vertices.
• Result: 3.

Case 8: Reconstructing from an Adjacency Matrix

Problem: If the matrix has a 1 at $A[1,3]$, what does it mean?

• Result: There is an edge connecting Vertex 1 and Vertex 3.

Case 9: The Self-Loop Rule

Problem: In a “Simple Graph,” can a vertex connect back to itself?

• Result: No. Simple graphs forbid loops and multiple edges between the same two points.

Case 10: Connectivity and Edges

Problem: What is the minimum number of edges to make a 10-vertex graph connected?

• Logic: To connect $n$ points, you need at least $n-1$ connections (think of a line).
• Result: 9.

---

7. Fundamental “How-To” Recipes 🍳

Recipe: The 2-Color Tiling (Bipartite Test)

1. Start anywhere: Color Vertex A Red.
2. Propagate: Color all neighbors of A Blue.
3. Repeat: Color neighbors of those Blue vertices Red.
4. The Conflict Test: If you are forced to give two neighbors the same color, the graph is NOT bipartite.

Recipe: Counting Routes with Matrices

1. Write Matrix $A$.
2. Square it ($A\times A$).
3. Read the entry: The value at $(i,j)$ in $A^k$ is the number of walks of length $k$ between $i$ and $j$.

---

8. Encyclopedia Mastery Challenge 🏆

1. The Handshake Proof: Prove that you can never have a group of 5 people where everyone has exactly 3 friends in the group.
2. The $K_n$ Logic: Why is the degree of every vertex in $K_n$ exactly $n-1$?
3. The Hamiltonian Quest: Research a “Hamiltonian Cycle.” How does it differ from the Euler Trail?
4. The Partition Paradox: If a bipartite graph has 10 vertices split into 5-and-5, what is the maximum number of edges it could have? (Hint: Can any U connect to any W?)

---

🚀 Master Status: You have completed the Encyclopedic Expansion of Network Topology. You now possess the tools to map the hidden connections of the world. 助