complete_graph

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.

Complete graph

Set

Discussion

Theorems

Reference

Parents

Subset of