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:

1. It is a graph whose geometric realization is a triangle: it has three vertices and an edge between each pair of vertices.
2. It is the cycle graph on 3 vertices, and is denoted $C_{3}$.
3. It is the complete graph on 3 vertices, and is denoted $K_{3}$.
4. It is the odd graph $O_{2}$, i.e., the Kneser graph $KG_{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{pmatrix}0&1&1\\1&0&1\\1&1&0\\\end{pmatrix}}$

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 {2n-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 {2n-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$: $2n-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{pmatrix}0&1&1\\1&0&1\\1&1&0\\\end{pmatrix}}$

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}-3t-2$	As $K_{n},n=3$: $(t+1)^{n-1}(t-n+1)=(t+1)^{2}(t-2)=t^{3}-3t-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)