Graphs, Walks and Connectivity

About this page

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.

✓ 21 results · all verified · 0 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 21 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

1 · Prerequisites

Combinatorics

Real Analysis

Set Theory

2 · Logical flowchart

3 · Items

Definition

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Remark

Unless stated otherwise, graph means finite, simple and undirected; orders, sizes and empty-set conventions are fixed here

Definition

Vertex cuts, edge cuts, vertex connectivity κ(G) and edge connectivity λ(G), with conventions for complete and one-vertex graphs

Definition

Graphs, Walks and Connectivity

3 · Items

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Unless stated otherwise, graph means finite, simple and undirected; orders, sizes and empty-set conventions are fixed here

Multigraphs, loops and directed graphs as variants distinct from the default finite simple graph

Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree

Subgraphs, induced subgraphs and spanning subgraphs

Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges

Every walk between two vertices contains a path between the same endpoints

Connected graphs and connected components defined by the existence of vertex paths

Being joined by a walk or path is the same equivalence relation on the vertex set

The connected components of a graph partition its vertex set and are its maximal connected subgraphs

Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention

Shortest-path distance is a metric on every connected component

A bipartite graph and a proper two-colouring of its vertices

Every closed walk of odd length contains a cycle of odd length

A finite graph is bipartite if and only if it has no odd cycle

Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices

The Petersen graph on the two-element subsets of a five-element set, adjacent when disjoint

Graph isomorphisms, automorphisms and graph complements

Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors

The line graph whose vertices are the edges of the original graph and whose adjacency records a shared endpoint

Handshake lemma: the sum of the vertex degrees is twice the number of edges

Every finite graph has an even number of vertices of odd degree

The complete graph on an n-element vertex set has C(n, 2) edges

There are 2^C(n, 2) simple graphs on a fixed labelled n-element vertex set

Vertex cuts, edge cuts, vertex connectivity κ(G) and edge connectivity λ(G), with conventions for complete and one-vertex graphs

A bridge as an edge whose deletion increases the number of connected components

An edge of a finite graph is a bridge if and only if it lies on no cycle

For every nontrivial connected graph, λ(G)≤δ(G)

For every nontrivial connected graph, κ(G)≤λ(G)

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

Every nonempty finite simple graph contains a path with at least δ(G) edges

Every finite simple graph of minimum degree at least two contains a cycle

An n-vertex simple graph with more than C(n-1, 2) edges is connected

FALSE: a finite simple graph is determined up to isomorphism by its degree sequence

FALSE: a connected simple graph in which every vertex has even degree must itself be a cycle

FALSE: vertex connectivity, edge connectivity and minimum degree are always equal

FALSE: a shortest walk between two vertices may repeat a vertex and fail to be a path