Learn Construct a graph from explicit adjacency rules, verify an upper coloring bound, and prove a matching lower bound by recoloring a hypothetical solution.
Open any lesson. Completion records participation; automatic practice checks and human judgment of written arguments are separate. This unit retains its own versioned requirements.
Try these short questions on paper, then compare your reasoning. They are optional self-checks, not a placement score or a navigation requirement. Use a targeted review when useful and return with your browser’s Back control.
Feasibility and optimality need different evidence.
No. A proper coloring supplies an upper bound. A matching lower bound must rule out every coloring with fewer colors.
A missing clique does not remove every coloring obstruction.
Yes. A five-cycle has no triangle, but two colors would have to alternate around its odd length and conflict at the closing edge.
Loading saved mathematics work…
Change the construction and audit the obstruction
The mixed assessment has separate response history and review criteria; it does not change lesson participation records.
Each linked lesson opens on its own page. Expand its details here when you want to check the objectives before choosing.
Construct the Mycielski shadow graph, count its edges and degrees, and prove triangle-freeness by checking every possible triangle type.
6 practice tasks.
Prove the exact chromatic increase of the Mycielski construction and distinguish a coloring certificate from a lower-bound proof.
6 practice tasks.