Triangle graph

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 is a particular finite undirected graph defined as follows:

It is a graph whose geometric realization is a triangle: it has three vertices and an edge between each pair of vertices.
It is the cycle graph on 3 vertices, and is denoted $C_{3}$ .
It is the complete graph on 3 vertices, and is denoted $K_{3}$ .
It is the odd graph $O_{2}$ , i.e., the Kneser graph $K G_{3, 1}$ .

Explicit descriptions

Descriptions of vertex set and edge set

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

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

Adjacency matrix

The adjacency matrix is:

$(\begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})$

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	3	As $C_{n}, n = 3$ : $n = 3$ As $K_{n}, n = 3$ : $n = 3$ As $O_{n}, n = 2$ : $(\binom{2 n - 1}{n - 1}) = (\binom{3}{1}) = 3$
size of edge set	3	As $C_{n}, n = 3$ : $n = 3$ As $K_{n}, n = 3$ : $(\binom{n}{2}) = (\binom{3}{2}) = 3$ As $O_{n}, n = 2$ : $(\binom{2 n - 1}{n - 1, n - 1, 1}) = (\binom{3}{1, 1, 1}) = 3$

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	2	As $C_{n}, n = 3$ : 2 (independent of $n$ ) As $K_{n}, n = 3$ : $n - 1 = 2$ As $O_{n}, n = 2$ : $n = 2$
eccentricity of a vertex	1	As $C_{n}, n = 3$ : greatest integer function of $n / 2$ equals greatest integer function of 3/2 equals 1 As $K_{n}, n = 3$ : 1 (true for any $n \geq 2$ ) As $O_{n}, n = 2$ : $n - 1 = 1$

Other numerical invariants

Function	Value	Explanation
clique number	3	As $C_{n}, n = 3$ : 3 (since $n = 3$ ; it's 2 for larger $n$ ) As $K_{n}, n = 3$ : $n = 3$ As $O_{n}, n = 2$ : 3
independence number	1	As $C_{n}, n = 3$ : greatest integer function of $n / 2$ equals greatest integer function of 3/2 equals 1 As $K_{n}, n = 3$ : 1 (independent of $n$ )
chromatic number	3	As $C_{n}, n = 3$ : 3 since $n$ is odd As $K_{n}, n = 3$ : $n = 3$
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 $C_{n}, n = 3$ : $n = 3$ As $K_{n}, n = 3$ : 3 (true for any $n \geq 3$ ) As $O_{n}, n = 2$ : $2 n - 1 = 2 (2) - 1 = 3$
even girth	infinite	there are no cycles of even length
girth of a graph	3	minimum of even and odd girth

Algebraic theory

The adjacency matrix is:

$(\begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})$

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^{3} - 3 t - 2$	As $K_{n}, n = 3$ : $(t + 1)^{n - 1} (t - n + 1) = (t + 1)^{2} (t - 2) = t^{3} - 3 t - 2$
minimal polynomial	$t^{2} - t - 2$	As $K_{n}, n = 3$ : $(t + 1) (t - n + 1) = t^{2} - (n - 2) t - (n - 1) = t^{2} - t - 2$
rank of adjacency matrix	3	As $K_{n}, n = 3$ : $n = 3$
eigenvalues (roots of characteristic polynomial)	-1 (multiplicity 2), 2 (multiplicity 1)	As $K_{n}, n = 3$ : -1 (multiplicity $n - 1 = 2$ ), $n - 1 = 2$ (multiplicity 1)