Independent Combinatorics and Graph Checkpoint

Allow 3–4 hours for an independent first attempt, then a separate feedback session. These hours are inside the module assessment allowance. Save attempts before opening the key; use the rubric. State every domain and hypothesis. Code checks examples afterward, not in place of the requested derivations.

1. A1: Count arrangements of AABBC. Count five-person subsets of eight people with one designated leader. Explain the uniform fibers used in each.
2. A2: Count nonnegative x+y+z=6 with each variable at most 3 by inclusion- exclusion. Prove some box contains at least four of ten objects in three boxes. Distinguish the counting answer from the existence guarantee.
3. A3: Derive counts bₙ of ternary words with no equal neighboring symbols. Include the empty word, the first nonempty case, recurrence range and proof. Explain why 3·2ⁿ⁻¹ cannot be used at n=0.
4. A4: Write an OGF for unordered coins of denominations 1 and 3 and extract the x⁶ coefficient. Compare with ordered sequences totaling six. Derive a recurrence or direct enumeration for the latter; state constant coefficients.
5. A5: For path 0–1–2–3 plus isolated vertex 4, give degrees, components, zero-step walk counts, and the number of two-step walks from 1 to 1. Explain why equal degree sequences alone do not prove graph isomorphism.
6. A6: Prove connectedness plus n−1 edges implies a tree for finite nonempty simple undirected graphs. Explain why every bridge appears in every spanning tree, and why the converse “every retained edge was a bridge” is false.
7. A7: For two triangles sharing exactly one vertex, classify Euler circuit and Hamilton cycle existence with proof. Recheck Euler existence if a separate edge component is added. Explain the edge/vertex distinction.
8. A8: Count labeled proper three-colorings of a triangle plus one isolated vertex. Determine the chromatic number with matching lower/upper arguments. Explain why merely dividing by 3! is not a general rule for color partitions.
9. A9: L={0,1,2}, R={10,11,12}, edges (0,10),(1,10),(2,11),(2,12). Give an optimal matching and a tight Hall-subset upper bound. Change one edge permission to allow all left vertices to be assigned; supply a witness.
10. A10: A simple graph has 12 vertices and 18 edges. Does the simple planar edge bound prove it planar? Give a nonplanar example with exactly those counts. State Euler's disconnected formula, its embedding assumption, and why counting faces from that equation cannot establish an embedding.