LemmaStatement: Literature-sourcedProof: 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.

For every nontrivial connected graph, $\kappa(G)\le\lambda(G)$

Statement

For every connected finite simple graph $G$ with at least two vertices, $\kappa(G)\le\lambda(G)$ .

Facts & Assumptions

Given: A connected graph $G=(V,E)$ with $n=|V|\ge2$ .

[F1]

$\kappa(G)$ is the least size of a vertex set whose deletion disconnects $G$ or leaves at most one vertex, and $\lambda(G)$ is the least size of an edge cut (Vertex cuts, edge cuts, vertex connectivity $\kappa(G)$ and edge connectivity $\lambda(G)$ , with conventions for complete and one-vertex graphs).

[F2]

The components of a disconnected graph partition its vertex set, and a walk between two different components must traverse an edge joining the two sides (The connected components of a graph partition its vertex set and are its maximal connected subgraphs, Connected graphs and connected components defined by the existence of vertex paths, Every walk between two vertices contains a path between the same endpoints).

Proof

technique · constructive

1.1

Choose an edge cut $F$ of size $\lambda(G)$ . Let $A$ be the vertex set of one component of $G-F$ and put $B=V\setminus A$ . Then $A$ and $B$ are nonempty, and every edge of $G$ between $A$ and $B$ belongs to $F$ .

givenF1F2chooseconstruct

2.1

If $|F|\ge n-1$ , deleting all but one vertex gives a vertex cut of size $n-1\le|F|$ , so $\kappa(G)\le\lambda(G)$ .

step 1.1F1

2.2

Suppose $|F|<n-1$ . The bipartite set of all pairs with one endpoint in $A$ and one in $B$ has $|A||B|\ge|A|+|B|-1=n-1$ members. Hence not every such pair is an edge of $G$ , for all cross edges lie in $F$ . Choose nonadjacent $a\in A$ and $b\in B$ .

step 1.1algebrachoose

3.1

For each edge $e\in F$ , choose one endpoint $s(e)$ different from both $a$ and $b$ ; this is possible because $e\ne\{a,b\}$ . Put $S=\{s(e):e\in F\}$ . Then $a,b\notin S$ , every edge of $F$ meets $S$ , and $|S|\le|F|$ .

step 2.2construct

4.1

Any path from $a\in A$ to $b\in B$ must use an edge between $A$ and $B$ , hence an edge of $F$ by step 1.1, and therefore a vertex of $S$ by step 3.1. Thus $G-S$ has no $a$ to $b$ path and is disconnected, so $S$ is a vertex cut.

step 1.1step 3.1F1F2

5.1

In the case $|F|<n-1$ , step 4.1 gives $\kappa(G)\le|S|\le|F|=\lambda(G)$ ; step 2.1 gives the same inequality in the remaining case.

step 2.1step 3.1step 4.1F1discharge-construct∎

Depends on

Used by

Whitney's inequalities: κ(G)≤λ(G)≤δ(G) for every nontrivial connected graph Theorem

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 22 results over 13 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

Wolfram MathWorld, Vertex Connectivity (standard reference, not scraped)

For every nontrivial connected graph, κ(G)≤λ(G)\kappa(G)\le\lambda(G)κ(G)≤λ(G)