ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-08-02

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

$K_{4}$ with one new vertex adjacent to two clique vertices satisfies Ore's condition but not Dirac's condition

Example

Start with the clique on $a, b, c, d$ and add a vertex $x$ adjacent exactly to $a$ and $b$ . The resulting five-vertex graph satisfies Ore's condition but not Dirac's minimum-degree condition, and it has the Hamilton cycle $x, a, c, d, b, x$ .

Facts & Assumptions

Given: The explicitly described five-vertex graph $G$ .

[F1]

A complete graph contains every edge between its distinct vertices (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[F2]

Degree counts neighbours, and minimum degree is the least vertex degree (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

[L1]

Ore's condition implies Hamiltonicity for graphs of order at least three (Ore's theorem: an $n$ -vertex graph with $n \geq 3$ and $\deg (u) + \deg (v) \geq n$ for every nonadjacent pair is Hamiltonian).

[L2]

Dirac's sufficient condition is $δ (G) \geq n / 2$ (Dirac's theorem: every $n$ -vertex graph with $n \geq 3$ and $δ (G) \geq n / 2$ is Hamiltonian).

Verification

technique · direct

1.1

The degree multiset is ${2, 3, 3, 4, 4}$ : $x$ has degree two, $a, b$ have degree four, and $c, d$ have degree three. Thus $δ (G) = 2 < 5 / 2$ , so Dirac's hypothesis [L2] fails.

givenF1F2L2algebra

1.2

Directly, every consecutive pair in $x, a, c, d, b, x$ is an edge, and the list visits all five vertices once before returning.

givenF1

2.1

The only nonedges are $x c$ and $x d$ . Each has endpoint-degree sum $2 + 3 = 5$ , so Ore's condition holds; [L1] therefore confirms Hamiltonicity.

step 1.1L1algebra

3.1

Hence Ore's condition can hold when Dirac's condition does not, and the displayed Hamilton cycle verifies the conclusion.

step 1.1step 2.1step 1.2∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

12 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Applied Combinatorics, Eulerian and Hamiltonian Graphs (standard reference, not scraped)

K4K4​ with one new vertex adjacent to two clique vertices satisfies Ore's condition but not Dirac's condition