Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
complete_graph [2014/02/08 13:13] nikolaj |
complete_graph [2014/02/09 02:42] nikolaj |
||
|---|---|---|---|
| Line 5: | Line 5: | ||
| | @#FFBB00: $ \langle V,E,\psi\rangle \in \mathrm{it}(E,V) $ | | | @#FFBB00: $ \langle V,E,\psi\rangle \in \mathrm{it}(E,V) $ | | ||
| - | | @#55EE55: $ \langle V,E,\psi\rangle $ ... loopless graph | | + | | @#55EE55: $ \langle V,E,\psi\rangle $ ... simple graph | |
| | @#FFFDDD: $ u,v \in V$ | | | @#FFFDDD: $ u,v \in V$ | | ||
| Line 15: | Line 15: | ||
| The axiom $\{u\}\notin\mathrm{im}(\psi)$ says that there are no loops on a single vertex. | 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 === | === Reference === | ||
| Wikipedia: [[http://en.wikipedia.org/wiki/Complete_graph|Complete graph]] | Wikipedia: [[http://en.wikipedia.org/wiki/Complete_graph|Complete graph]] | ||
| ==== Parents ==== | ==== Parents ==== | ||
| === Subset of === | === Subset of === | ||
| - | [[Loopless graph]] | + | [[Simple graph]] |
