Complete graph:K4

This article defines a particular undirected graph, i.e., the definition here determines the graph uniquely up to graph isomorphism.
View a complete list of particular undirected graphs

Definition

This graph, denoted $K_4$ is defined as the complete graph on a set of size four. It is also sometimes termed the tetrahedron graph or tetrahedral graph.

Explicit descriptions

Descriptions of vertex set and edge set

Vertex set: $\{1,2,3,4\}$

Edge set: $\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\}$

Adjacency matrix

The adjacency matrix is:

$\left(\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 0\\ \end{array}\right)$

The matrix is uniquely defined (note that it centralizes all permutations).

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	4	As $K_n,n=4$: $n=4$
size of edge set	6	As $K_n,n=4$: $(\genfrac{}{}{0ex}{}{n}{2})=(\genfrac{}{}{0ex}{}{4}{2})=6$

Numerical invariants associated with vertices

Since the graph is a vertex-transitive graph, any numerical invariant associated to a vertex must be equal on all vertices of the graph. Below are listed some of these invariants:

Function	Value	Explanation
degree of a vertex	3	As $K_n,n=4$: $n-1=3$
eccentricity of a vertex	1	As $K_n,n=4$: 1 (true for all $n\ge 2$, independent of $n$)

Other numerical invariants

Function	Value	Explanation
clique number	4	As $K_n,n=4$: $n=4$
independence number	1	As $K_n,n=4$: 1 (independent of $n$)
chromatic number	4	As $K_n,n=4$: $n=4$
radius of a graph	1	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	1	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
odd girth	3	As $K_n,n=4$: 3 (because $n\ge 3$)
even girth	4	As $K_n,n=4$: 4 (because $n\ge 4$)
girth of a graph	3	As $K_n,n=4$: 3 (because $n\ge 3$)

Algebraic theory

The adjacency matrix is:

$\left(\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 0\\ \end{array}\right)$

The matrix is uniquely defined (note that it centralizes all permutations). Below are some important associated algebraic invariants:

Algebraic invariant	Value	Explanation
characteristic polynomial	$t^4-6t^2-8t-3$	As $K_n,n=4$: $(t+1{)}^{n-1}(t-n+1)=(t+1{)}^3(t-3)=t^4-6t^2-8t-3$
minimal polynomial	$t^2-2t-3$	As $K_n,n=4$: $(t+1)(t-n+1)=t^2-(n-2)t-(n-1)=t^2-2t-3$
rank of adjacency matrix	4	As $K_n,n=4$: $n=4$
eigenvalues (roots of characteristic polynomial)	-1 (multiplicity 3), 3 (multiplicity 1)	As $K_n,n=4$: -1 (multiplicity $n-1=3$), $n-1=3$ (multiplicity 1)