TheoremStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck 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\ge1$ 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\ge1$ 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 q2$ 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 $\lvert B\rvert \le \lvert A\rvert$ , 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\setminus A$ , and write $k=|A|$ . Then $1\le k\le 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 k2$ , and those with both endpoints in $B$ number at most $\binom{n-k}2$ . Step 1.1 accounts for every edge, so $|E|\le\binom k2+\binom{n-k}2$ .

step 1.1L1

2.2

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

step 1.1algebra

3.1

Steps 2.1 and 2.2 give $|E|\le\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 · next 3 levels

Direct dependencies and their dependencies through the next three levels: 72 results over 23 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

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

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