TheoremStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-04 (gpt-5.6-sol-codex-subscription)

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.

An $n$ -vertex simple graph with more than $(\binom{n - 1}{2})$ edges is connected

Statement

Let $G$ be a finite simple graph with $n \geq 1$ vertices. If $∣ E (G) ∣ > (\binom{n - 1}{2})$ , then $G$ is connected.

Facts & Assumptions

Given: A finite simple graph $G = (V, E)$ with $∣ V ∣ = n \geq 1$ and $∣ E ∣ > (\binom{n - 1}{2})$ .

[F1]

If $G$ is disconnected, its components partition $V$ into at least two nonempty sets and no edge joins different components (Connected graphs and connected components defined by the existence of vertex paths, The connected components of a graph partition its vertex set and are its maximal connected subgraphs).

[L1]

A simple graph on a $q$ -element vertex set has at most $(\binom{q}{2})$ edges, with equality for the complete graph (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets, A finite set with $n$ elements has exactly $(\binom{n}{2})$ two-element subsets, and $2 (\binom{n}{2}) = n (n - 1)$ , A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ , The complete graph on an $n$ -element vertex set has $(\binom{n}{2})$ edges).

Proof

technique · contradiction

1.1

Suppose, for contradiction, that $G$ is disconnected. Choose one component with vertex set $A$ , put $B = V ∖ A$ , and write $k = ∣ A ∣$ . Then $1 \leq k \leq n - 1$ , $∣ B ∣ = n - k$ , and no edge joins $A$ to $B$ .

assume-contraF1choose

2.1

By [L1], the edges with both endpoints in $A$ number at most $(\binom{k}{2})$ , and those with both endpoints in $B$ number at most $(\binom{n - k}{2})$ . Step 1.1 accounts for every edge, so $∣ E ∣ \leq (\binom{k}{2}) + (\binom{n - k}{2})$ .

step 1.1L1

2.2

For $1 \leq k \leq n - 1$ , elementary binomial algebra gives $(\binom{k}{2}) + (\binom{n - k}{2}) = (\binom{n - 1}{2}) - (k - 1) (n - k - 1) \leq (\binom{n - 1}{2})$ .

step 1.1algebra

3.1

Steps 2.1 and 2.2 give $∣ E ∣ \leq (\binom{n - 1}{2})$ , contradicting the hypothesis. Therefore $G$ is connected.

step 2.1step 2.2givendischarge-contradiction∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

36 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

Cornell Mathematics, Graph Theory notes (standard reference, not scraped)

An nn-vertex simple graph with more than (n−12)(2n−1​) edges is connected