Alphabeta MathPersonal research
Article items · 01 — The complete graph on an $n$-element vertex set has $\binom{n}{2}$ edges
Presents 28 items from the article and its immediate prerequisites, covering published library prerequisites.
1 · Prerequisites
- A finite set with n elements has exactly C(n, 2) two-element subsets, and 2C(n, 2) = n(n-1)
- Being joined by a walk or path is the same equivalence relation on the vertex set
- lvertP(A)| = 2^| A| for finite A
- Equinumerous sets, A ≈ B and A ⪯ B
- Trichotomy of the order on ℕ
- Unless stated otherwise, graph means finite, simple and undirected; orders, sizes and empty-set conventions are fixed here
- Every walk between two vertices contains a path between the same endpoints
- Simple graphs on an arbitrary vertex set
- Finite, countably infinite, countable, uncountable
- The pigeonhole principle on ℕ
- Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree
- A function is a relation f with (a,b) ∈ f and (a,c) ∈ f implying b = c; f : A → B, the value f(a), domain and codomain
- The image R[A] and the preimage R⁻¹[B] of a set under a relation
- Addition of natural numbers
- Inductive set
- The natural numbers exist: a smallest inductive set
- Peano system
- The Axiom of Infinity: there is a set containing a set with no elements and closed under y ↦ y ∪ {y}
- The Axiom Schema of Separation: for each formula φ, ∀ p̄ ∀ x ∃ y ∀ z (z ∈ y ↔ (z ∈ x ∧ φ(z,p̄)))
- A bipartite graph and a proper two-colouring of its vertices
- The von Neumann naturals form a Peano system
- Left identity for addition
- Left successor law for addition
- Discreteness: σ(n) is the immediate successor
- Every natural number is a transitive set and is not a member of itself
- No natural number equals its own successor
- Every walk contains a path between the same endpoints, of no greater length
- Addition is associative
- Every nonzero natural number is a successor
- Order is compatible with addition
- The well-ordering principle
- The sum ∑_i ∈ S aᵢ over a finite index set, and its product form
- A finite sum is unchanged by a permutation of its index range: ∑_k<n a_π(k) = ∑_k<n aₖ for every bijection π : n → n
- Finite sums and finite products of natural numbers, ∑_k<n aₖ and ∏_k<n aₖ in ℕ
- Laws of finite sums and products in ℕ, and ι(∑_k<n aₖ) = ∑_k<n ι(aₖ)
- Finite sums and finite products, by recursion
- Laws of finite sums and finite products
2 · Logical flowchart
Arrows show item dependencies. A grouped prerequisite node points to items that use one or more of its members; their exact links are listed above.
3 · Items
CorollaryLibrary prerequisite
The complete graph on an n-element vertex set has C(n, 2) edges
CorollaryLibrary prerequisite
The connected components of a graph partition its vertex set and are its maximal connected subgraphs
DefinitionLibrary prerequisite
The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|
DefinitionLibrary prerequisite
Cliques, independent sets, clique number and independence number
DefinitionLibrary prerequisite
The complete connection of two disjoint graphs
DefinitionLibrary prerequisite
Connected graphs and connected components defined by the existence of vertex paths
DefinitionLibrary prerequisite
Cycles, trees and forests in a simple graph on an arbitrary vertex set
DefinitionLibrary prerequisite
The cardinality | A| of a finite set
DefinitionLibrary prerequisite
A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
DefinitionLibrary prerequisite
Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
DefinitionLibrary prerequisite
Graph isomorphisms, automorphisms and graph complements
DefinitionLibrary prerequisite
Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
DefinitionLibrary prerequisite
Induced embeddings and induced copies of a graph
DefinitionLibrary prerequisite
Injection, surjection, bijection
DefinitionLibrary prerequisite
Order on the natural numbers
DefinitionLibrary prerequisite
The natural numbers ℕ (von Neumann)
DefinitionLibrary prerequisite
Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices
DefinitionLibrary prerequisite
Subgraphs, induced subgraphs and spanning subgraphs
DefinitionLibrary prerequisite
r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s
DefinitionLibrary prerequisite
Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set
LemmaLibrary prerequisite
Addition is cancellative
LemmaLibrary prerequisite
Addition is commutative
LemmaLibrary prerequisite
On ℕ the order is membership: m < n ⟺ m ∈ n
TheoremLibrary prerequisite
A nonempty simple graph is a tree if and only if each pair of vertices is joined by exactly one path
TheoremLibrary prerequisite
The principle of mathematical induction
TheoremLibrary prerequisite
≤ is a linear order on ℕ
TheoremLibrary prerequisite
A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
TheoremLibrary prerequisite