Counting and Graph Model Contracts

Before calculating, state the object being counted, when two objects are equal, and all constraints. Before using a graph theorem, state the graph flavor and what its vertices and edges mean. This makes every formula auditable.

Choice	Distinction that changes the answer
Labels	Two named time slots versus two interchangeable groups
Repetition	Sampling with replacement versus distinct selections
Order	A sequence of coins versus an unordered multiset of coins
Constraints	Upper/lower bounds, exclusions and required coverage
Empty objects	One empty selection/function/word, when the specified set includes it
Graph flavor	Directed, simple undirected, or multigraph with edge identities
Claim type	Count, existence, witness, bound, optimality or impossibility

Counting rules with their obligations

For multiplication, later choices need not be probabilistically independent. It suffices that every valid partial choice at a stage has the stated number of extensions, and that complete construction paths correspond uniquely to outcomes. Choosing two distinct people in order gives n(n−1): the available second people depend on the first, but their number is constant.

Division requires equal-size representation classes. Four-bit necklaces under rotation have classes of sizes 1,2 and 4, so dividing 16 by 4 is invalid. Inclusion-exclusion requires well-defined finite sets and their intersections; a common containing universe can always be chosen by taking their union.

Use exact integer arithmetic for finite counts. A formal power series records coefficients; numerical convergence is not required for coefficient identities. Multiplication counts size-additive ordered pairs. Any sequence has an OGF; the combinatorial product rule determines whether ordinary or exponential normalization is appropriate, not a slogan that OGFs are only for unlabeled objects.

Graph conventions

Core labs use finite simple undirected graphs with an explicit vertex carrier. Loops and parallel edges are rejected. A singleton is a tree; the empty graph is a forest with zero components and is not called a tree here. Isolated vertices contribute components even when absent from all edges.

A walk may repeat vertices and edges. A simple path has no repeated vertex. An Euler trail uses every edge once; a Hamilton path uses every vertex once. For nonempty edge sets, Euler classification needs connectivity of the vertices incident to edges. Isolates do not prevent edge coverage. The API reports a separate empty result when there are no edges, avoiding an implicit convention.

Color names are labeled, and a proper k-coloring need not use every available color. A witness proves feasibility, not minimum color count. A matching witness proves a lower bound on achievable matching size. To prove optimality, pair it with an upper bound: for any left subset S, no more than |N(S)| of its vertices can be matched, so every matching has size at most |L|−|S|+|N(S)|.

Planarity and execution limits

Euler's formula v−e+f=1+c describes a plane embedding with c components, including the outer face. Faces are not data supplied by an arbitrary graph's edge list. Planar edge bounds are necessary conditions, never general certificates of planarity. A crossing-free drawing or a justified theorem can establish it.

The offline kit deliberately limits input sizes for exhaustive checks. Passing bounded tests does not prove every implementation correct for all sizes. Every mathematical proof must state its wider domain and termination or coverage argument separately. Efficient graph algorithms belong to Semester 2; here the focus is constructing and verifying the model.