Combinatorics and Graph Theory: Case Studies

Case 1: A correct number for the wrong object

Two labeled rooms hold five distinct tasks, at most three per room. A developer counts two size vectors, (2,3) and (3,2), and reports two schedules. That counts identical units in distinct bins. Named-task assignments require choosing which tasks occupy each room: 20 before conflicts are imposed. Produce both models and a forward map from assignments to size vectors; explain the sizes of its fibers. Then apply the conflict graph in the capstone rather than multiplying independent counts without justification.

Case 2: The cheapest connected network loses route quality

A triangle has link weights AB=2,BC=2,AC=3. Its MST keeps AB and BC, total weight four. The original direct A-to-C route costs three, while the tree route costs four. The MST solves total connection cost; it does not optimize each root distance or redundancy. Submit an exchange argument and a shortest-route comparison. Do not replace a service reliability model with an edge-count theorem.

Case 3: Parity overlooks disconnected work

Two disjoint triangular inspection networks have even degrees everywhere. A parity-only classifier incorrectly reports one Euler circuit covering all six edges. Give the component obstruction and the corrected condition on edge-bearing vertices. Contrast this with a triangle plus an isolated vertex: edge coverage still works, but a vertex-coverage requirement would be different.

Case 4: A planar-looking count hides a forbidden structure

Subdivide all ten edges of K₅ once. The new graph has 15 vertices and 20 edges, well below 3v−6. It remains a subdivision of K₅ and is nonplanar. Submit the edge/vertex accounting and the obstruction. Passing a necessary numeric test cannot certify an embedding or a physical layout.