Complete graph

Set

context $V,E$ … set
definiendum $ \langle V,E,\psi\rangle \in \mathrm{it}(E,V) $
postulate $ \langle V,E,\psi\rangle $ … simple graph
for all $ u,v \in V$
postulate $ u\neq v\implies \exists !(e\in E).\ \psi(e)=\{u,v\} $

Discussion

In a complete (undirected) graph, every two distinct vertices are connected.

The axiom $\{u\}\notin\mathrm{im}(\psi)$ says that there are no loops on a single vertex.

Theorems

When dealing with simple graphs, if you add another vertex to a graph with $n$ vertices, you can add $n$ new edges at best. So a complete graph with $n$ vertices has maximally $\sum_{k=1}^{n-1}k=\frac{1}{2}n(n-1)$ edges.

Reference

Wikipedia: Complete graph

Parents

Subset of

Link to graph
Log In
Improvements of the human condition