# Four pairwise adjacent vertices need more colors

KL-FCS-048 · Constraint satisfaction · version 1.0.0

## Problem

Decide and count color assignments satisfying every graph edge.

## Context

Expose both satisfiable assignments and complete impossibility arguments for finite variable domains.

## Definitions

- **Constraint**: A relation restricting allowed variable assignments.
- **Graph coloring**: Adjacent vertices must receive different colors.
- **Solution space**: Every assignment satisfying all declared constraints.

## Checked result

Satisfiable: no; Solution count: 0.

Every assignment either yields a fully valid coloring or an edge witnessing failure. Counting includes distinct color labels, so symmetric assignments remain separate.

## Checker reasoning

1. Enumerate one color value for each vertex.
2. Check every edge’s unequal-color constraint.
3. Count the complete solution space.
4. Validate a coloring witness, or require enumeration evidence when no model exists.

## Dataset construction

{
  "family": "constraints",
  "task": "Decide and count color assignments satisfying every graph edge.",
  "input_encoding": "Structured JSON; field meanings are stated in the specification.",
  "coverage": "Complete assignment space · 81 candidates",
  "acceptance": [
    "Enumerate one color value for each vertex.",
    "Check every edge’s unequal-color constraint.",
    "Count the complete solution space.",
    "Validate a coloring witness, or require enumeration evidence when no model exists."
  ],
  "generation": "Deterministic finite fixture; full enumeration or witness replay as stated.",
  "split_policy": "Reference corpus for exposition and reproduction; no train/test evaluation split is claimed."
}

## Formal payload

```json
{
  "specification": {
    "vertices": 4,
    "edges": [
      [
        0,
        1
      ],
      [
        0,
        2
      ],
      [
        0,
        3
      ],
      [
        1,
        2
      ],
      [
        1,
        3
      ],
      [
        2,
        3
      ]
    ],
    "colors": 3
  },
  "claim": {
    "satisfiable": false,
    "solution_count": 0
  },
  "witness": {
    "method": "exhaustive enumeration"
  }
}
```

## Complexity

k colors on n vertices produce kⁿ assignments. Color-label permutations can create symmetric solutions.

## Limits

This is a finite coloring instance; the solution count is not reduced by graph or color symmetries.

## Common error and further work

Failing to find a solution is not equivalent to proving there is none.

Add symmetry reduction and checked propagation or conflict explanations.

## Verification

Complete assignment space · 81 candidates. 81 checker units.
Replay with `python3 tools/verify.py`. Mechanical status: checked; human review
has not yet been recorded. Custom Python verification, not a proof-assistant
claim. Checker 1.0.0 and exact source hashes are in `verification.json`.

## Provenance and references

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11.
No external dataset or model-generation experiment. Reuse-license selection
remains pending.

- [Conceptual reference](https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/download/)