Counting Proper Colorings via the Multiplication Principle

A proper coloring of a graph assigns a color to every vertex so that no edge joins two vertices of the same color. In konkur problems the "graph" is usually a figure of cells: each cell is a vertex, and two cells are adjacent (joined by an edge) when they share a side. The task is to count how many proper colorings exist with $k$ available colors.

The key idea is the multiplication principle: process the vertices in a carefully chosen order, and as you color each one, count how many colors are still legal given the choices already locked in. If those counts do not depend on the specific colors picked earlier — only on how many neighbors are already colored — the total is just the product of the per-vertex counts.

The per-vertex rule

Suppose you are about to color a vertex $v$ and exactly $d$ of its neighbors have already been colored. To stay proper, $v$ must avoid those neighbors' colors. In the cleanest case those $d$ neighbors carry $d$ distinct colors, so $v$ has

$k - d \quad\text{legal choices.}$

Multiplying these counts down a good ordering gives the total number of proper colorings. Two especially common building blocks:

• Pendant (degree-1) vertex. A cell whose only neighbor is colored last-but-one always sees exactly one forbidden color, so it contributes a factor of $k-1$, no matter how the rest is colored. Strip pendants off and handle them as independent $(k-1)$ factors.
• A path / tree of $n$ vertices. Color a root in $k$ ways, then each subsequent vertex has exactly one already-colored neighbor, contributing $k-1$. A tree (no cycles) therefore has exactly $k\,(k-1)^{\,n-1}$ proper colorings.

How to apply

1. Build the adjacency graph. Mark which cells share an edge; list the edges.
2. Peel off pendants. Every degree-1 vertex multiplies the answer by $(k-1)$; remove it and repeat. This often shrinks the figure to a small core.
3. Order the core so each new vertex has few colored neighbors. Color the first vertex in $k$ ways; for each later vertex subtract the number of distinctly-colored neighbors already placed.
4. Multiply all the factors. Watch for vertices whose two colored neighbors might share a color (then the subtraction changes) — if so, split into cases.

Mini-example: a triangle with a tail

Take a triangle $a\text{-}b\text{-}c$ (each pair adjacent) plus a pendant cell $d$ attached only to $c$, with $k=3$ colors. Color $a$: $3$ ways. Color $b$ (neighbor $a$): $3-1=2$ ways. Color $c$ (neighbors $a,b$, which are distinct): $3-2=1$ way. Finally the pendant $d$ (one neighbor $c$): $3-1=2$ ways. The product is

$3\cdot 2\cdot 1\cdot 2 = 12$

proper colorings. The triangle forces all three colors, then the tail just avoids its single neighbor.

Exam trick: order matters only for counting, not for the figure — always color a vertex after enough of its neighbors so the choice count $k-d$ is forced and constant. If a vertex's already-colored neighbors could be either equal or different colors, do not write a single $k-d$; split into cases (neighbors same vs. different) and add the resulting products.