Combinatorics: constructions, bounds and certificates
Bring ideas together without being told which method to use. Show the reasoning that makes your result valid.
Suggested session length: 270 minutes, as an unvalidated planning estimate. This collection contains 15 tasks; choose a manageable set and return for further sessions. Completing the whole collection may take substantially longer. This is a unit assessment, not a full course or AP examination.
Attempt these mixed tasks before opening worked guidance. State assumptions and justify all steps; numerical agreement alone is not a proof.
These public problems require human mathematical review. Saved responses and revealed solutions do not establish secure independent examination performance.
Work is untimed. Use the suggested duration for planning, then review errors, return to linked lessons and revise.
Loading saved assessment responses…
0 of 15 tasks have recorded responses. No overall mastery score is assigned.
Prove every finite simple bridgeless cubic graph has a perfect matching, using the now-proved Tutte theorem. Here cubic means degree3at every vertex, and a bridge is an edge whose deletion increases component count. For any deleted set S, count edges from an odd component of G−S to S. Then show why the bridgeless hypothesis matters: take three disjoint copies of K4 with one edge subdivided in each, and join all three subdivision vertices to one new central vertex.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Use four symbols0,1,2,3 and five ordered positions. Count words with positive multiplicities(2, 2, 1), distinguishing a profile from the fixed vector(2, 2, 1, 0). For that fixed vector, how many words begin with a nonzero symbol? Count all frequency equivalence classes on length-five words, then the nonempty classes after leading zero is forbidden. Explain why neither count follows by dividing all words by30.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Use four bits and the fifteen four-literal clauses that forbid every assignment except (0, 1, 0, 1). Compute the expected satisfied count under fair independent bits and prove existence of an assignment satisfying all fifteen without assuming clause independence. Explain what changes if the sixteenth clause is added. Give a conditional-expectation construction rule; then explain why the nominal three-literal clause (x OR x OR x) invalidates a proposed universal 7/8 clause probability.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
A length11 row contains four marked objects and seven unmarked objects. It starts marked. Internal gaps in order require at least0,2,1 unmarked objects, and the trailing gap requires at least2. Count positional patterns and prove the encoding. If all objects are distinctly labeled and both label orders are unrestricted, how many rows result? The gap bounds refer to ordinal marked positions, not particular labels. Finally change only the leading rule to at least one unmarked object before the first mark, and count the new positional patterns.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
On a five-element ground set {a,b,c,d,e}, allow at most one of {a,b} and at most two of {c,d,e}, with weights (7,6,4,−2,−3). Prove augmentation, find the maximum-weight basis and unrestricted independent optimum, and explain the signed-weight distinction. For retained A={a}, comparison basis B={a,d,e} and incoming g=c, exhibit every prefix-preserving exchange and its weight change. Explain which comparison is needed for the greedy optimality invariant. Separately allow every subset of {p,q} or {q,r,s}, with weights (6,5,4,4). Give a failed-augmentation witness, the decreasing greedy result and a better feasible competitor. State what exhaustive verification of these finite cases cannot prove.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Count solutions x₁+⋯+x₄=7 with 0≤xᵢ≤3 using inclusion–exclusion and coefficient extraction. Then derive Σk C(n,k)=n2^(n−1) by counting marked subsets, and explain why inversion counts of permutations are generated by ∏ⱼ₌₁ⁿ(1+q+⋯+q^(j−1)).
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Count partitions of eight distinct labels into two singleton blocks and three pair blocks. Derive the EGF for partitions with blocks of size one or two, and contrast it with the OGF for integer partitions using parts one or two. Explain why cycles of size j contribute zʲ/j rather than zʲ/j! to a permutation EGF.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Find the number of derangements of five labels. Derive the OGF for a₀=1,a₁=1,aₙ=aₙ₋₁+2aₙ₋₂, and find a₅. Finally count paths with five up and five down steps that never go below zero, using an explicit reflection bijection.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For subsets of a finite set, let g(S)=ΣT⊆S f(T). Prove f(S)=ΣT⊆S(−1)^|S−T|g(T). Use maximal chains to bound antichains in the Boolean lattice on seven labels. Count binary colorings of five cyclic positions up to rotation, and explain why reflection is excluded.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Count labelled trees on six vertices with degrees (3,2,2,1,1,1). For K₃,₃ derive its spanning-tree count from a Laplacian cofactor. Explain a cut-exchange proof of minimum spanning tree greedy choice and why it does not justify greedy choice in arbitrary independence systems.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
A network has capacities s→a=5,s→b=4,a→b=2,a→t=3,b→t=6. Give a maximum flow and matching cut. Then for left vertices a,b,c,d with neighborhoods {1,2},{1,2},{2,3},{3}, find a maximum matching, a minimum cover and a Hall obstruction. Explain how split vertices convert internally disjoint paths to a flow problem.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Two disjoint triangles are joined by a single edge between designated vertices. Determine whether the graph has a perfect matching, an Euler trail and a Hamilton cycle. Explain why a matching blossom is triggered by a nonmatching edge between outer vertices of one alternating tree, and why equal parity alone is insufficient.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Find the chromatic polynomial of the five-cycle and its value at four colors. Prove K₃,₄ is nonplanar using a suitable face bound. Explain how a connected plane graph and its dual relate spanning trees, and why a drawing with crossings alone is not a nonplanarity proof.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Determine the maximum edges in a K₄-free graph on eleven vertices and provide an extremal construction. Derive R(3,5)≤15 using the standard Ramsey recurrence and base values, and explain why a recurrence upper bound does not prove equality.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For G(5,p), derive the expected triangle count and its variance. Evaluate both at p=1/2 and use a second-moment bound for the probability that a triangle exists. Explain why disjoint-edge independence matters and how a random-cut expectation gives a deterministic existence result.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Review and revisit
Use each rubric to identify a valid argument, a missing condition or a step to revise. For independent evaluation, ask a teacher or reviewer to examine the complete reasoning. Self-review and recorded responses are not verified assessment results.
Coverage and targeted lesson returns
Prove every finite simple bridgeless cubic graph has a perfect matching, using the now-proved Tutte theorem. Here cubic means degree3at every vertex, and a bridge is an edge whose deletion increases component count. For any deleted set S, count edges from an odd component of G−S to S. Then show why the bridgeless hypothesis matters: take three disjoint copies of K4 with one edge subdivided in each, and join all three subdivision vertices to one new central vertex.
Use four symbols0,1,2,3 and five ordered positions. Count words with positive multiplicities(2, 2, 1), distinguishing a profile from the fixed vector(2, 2, 1, 0). For that fixed vector, how many words begin with a nonzero symbol? Count all frequency equivalence classes on length-five words, then the nonempty classes after leading zero is forbidden. Explain why neither count follows by dividing all words by30.
Use four bits and the fifteen four-literal clauses that forbid every assignment except (0, 1, 0, 1). Compute the expected satisfied count under fair independent bits and prove existence of an assignment satisfying all fifteen without assuming clause independence. Explain what changes if the sixteenth clause is added. Give a conditional-expectation construction rule; then explain why the nominal three-literal clause (x OR x OR x) invalidates a proposed universal 7/8 clause probability.
A length11 row contains four marked objects and seven unmarked objects. It starts marked. Internal gaps in order require at least0,2,1 unmarked objects, and the trailing gap requires at least2. Count positional patterns and prove the encoding. If all objects are distinctly labeled and both label orders are unrestricted, how many rows result? The gap bounds refer to ordinal marked positions, not particular labels. Finally change only the leading rule to at least one unmarked object before the first mark, and count the new positional patterns.
On a five-element ground set {a,b,c,d,e}, allow at most one of {a,b} and at most two of {c,d,e}, with weights (7,6,4,−2,−3). Prove augmentation, find the maximum-weight basis and unrestricted independent optimum, and explain the signed-weight distinction. For retained A={a}, comparison basis B={a,d,e} and incoming g=c, exhibit every prefix-preserving exchange and its weight change. Explain which comparison is needed for the greedy optimality invariant. Separately allow every subset of {p,q} or {q,r,s}, with weights (6,5,4,4). Give a failed-augmentation witness, the decreasing greedy result and a better feasible competitor. State what exhaustive verification of these finite cases cannot prove.
Count solutions x₁+⋯+x₄=7 with 0≤xᵢ≤3 using inclusion–exclusion and coefficient extraction. Then derive Σk C(n,k)=n2^(n−1) by counting marked subsets, and explain why inversion counts of permutations are generated by ∏ⱼ₌₁ⁿ(1+q+⋯+q^(j−1)).
Count partitions of eight distinct labels into two singleton blocks and three pair blocks. Derive the EGF for partitions with blocks of size one or two, and contrast it with the OGF for integer partitions using parts one or two. Explain why cycles of size j contribute zʲ/j rather than zʲ/j! to a permutation EGF.
Find the number of derangements of five labels. Derive the OGF for a₀=1,a₁=1,aₙ=aₙ₋₁+2aₙ₋₂, and find a₅. Finally count paths with five up and five down steps that never go below zero, using an explicit reflection bijection.
For subsets of a finite set, let g(S)=ΣT⊆S f(T). Prove f(S)=ΣT⊆S(−1)^|S−T|g(T). Use maximal chains to bound antichains in the Boolean lattice on seven labels. Count binary colorings of five cyclic positions up to rotation, and explain why reflection is excluded.
Count labelled trees on six vertices with degrees (3,2,2,1,1,1). For K₃,₃ derive its spanning-tree count from a Laplacian cofactor. Explain a cut-exchange proof of minimum spanning tree greedy choice and why it does not justify greedy choice in arbitrary independence systems.
A network has capacities s→a=5,s→b=4,a→b=2,a→t=3,b→t=6. Give a maximum flow and matching cut. Then for left vertices a,b,c,d with neighborhoods {1,2},{1,2},{2,3},{3}, find a maximum matching, a minimum cover and a Hall obstruction. Explain how split vertices convert internally disjoint paths to a flow problem.
Two disjoint triangles are joined by a single edge between designated vertices. Determine whether the graph has a perfect matching, an Euler trail and a Hamilton cycle. Explain why a matching blossom is triggered by a nonmatching edge between outer vertices of one alternating tree, and why equal parity alone is insufficient.
Find the chromatic polynomial of the five-cycle and its value at four colors. Prove K₃,₄ is nonplanar using a suitable face bound. Explain how a connected plane graph and its dual relate spanning trees, and why a drawing with crossings alone is not a nonplanarity proof.
Determine the maximum edges in a K₄-free graph on eleven vertices and provide an extremal construction. Derive R(3,5)≤15 using the standard Ramsey recurrence and base values, and explain why a recurrence upper bound does not prove equality.
For G(5,p), derive the expected triangle count and its variance. Evaluate both at p=1/2 and use a second-moment bound for the probability that a triangle exists. Explain why disjoint-edge independence matters and how a random-cut expectation gives a deterministic existence result.
