Skip to the content

Math 2.0

Combinatorics Graph theory: basic notions Example

Complete graph

Example

Let $n$ be a natural number. The complete graph $K_n$ is the graph with vertex set $\{1, \dots, n\}$ in which any two distinct vertices are adjacent.

More generally, the complete graph on a set $V$ has an edge between each pair of distinct elements of $V$ .

Remarks

The graph $K_n$ is $(n-1)$ -regular, and it has $\binom{n}{2}$ edges. The node number of edges of a complete graph states this. $K_3$ is a triangle. $K_4$ is planar, and $K_5$ is not planar. A clique in a graph is a set of vertices that induces a complete graph.

Where this leads

12 pages build on this one.

Further reading

Web https://en.wikipedia.org/wiki/Complete_graph, lead section

About this page

Tag	`03WKB2H474`
URI	`m2://03WKB2H474`
Kind	example
Writing	W2 usable
MSC	05C99
Instance of	Graph
Same as	Wikidata Q45715 Wikipedia Complete graph

Markdown · JSON · Edit on GitHub

What this page needs for W3

a person confirmed each agent-written section: rule P04 (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by