Complete graph
Set
| definiendum | $ \langle V,E,\psi\rangle \in \mathrm{it}(E,V) $ |
| postulate | $ \langle V,E,\psi\rangle $ … simple graph |
| 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
Parents
Subset of
