Square 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 undirected graph is defined in the following equivalent ways:

1. It is the cycle graph on 4 vertices, denoted $C_4$.
2. It is the complete bipartite graph $K_{2,2}$
3. It is the 2-dimensional hypercube graph.
4. It is the 2-dimensional hyperoctahedron graph.

Explicit descriptions

Description of vertex set and edge set

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

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

Note that with this description, the two parts in a bipartite graph description are $\{1,3\}$ and $\{2,4\}$.

Adjacency matrix

With the ordering of the vertex set and edge set given above, the adjacency matrix is:

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

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	4	As cycle graph $C_n,n=4$: $n=4$ As complete bipartite graph $K_{m,n},m=n=2$: $m+n=2+2=4$ As $n$-dimensional hypercube, $n=2$: $2^n=2^2=4$
size of edge set	4	As cycle graph $C_n,n=4$: $n=4$ As complete bipartite graph $K_{m,n},m=n=2$: $mn=2(2)=4$ As $n$-dimensional hypercube, $n=2$: $n\cdot 2^{n-1}=2\cdot 2^{2-1}=4$

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 cycle graph $C_n,n=4$: 2 (independent of $n$) As complete bipartite graph $K_{m,n},m=n=2$: Since $m,n$ are equal, the graph is vertex-transitive and $(m=n)$-regular, so we get $m=n=2$ As $n$-dimensional hypercube, $n=2$: $n=2$ As $n$-dimensional hyperoctahedron, $n=2$: $2n-2=2(2)-2=2$
eccentricity of a vertex	2	As cycle graph $C_n,n=4$: greatest integer of $n/2$ equals greater integer of 4/2 equals 2 As complete bipartite graph $K_{m,n},m=n=2$: 2 (independent of $m,n$, though it uses that both numbers are greater than 1) As $n$-dimensional hypercube, $n=2$: $n=2$ As $n$-dimensional hyperoctahedron, $n=2$: 2 (independent of $n$, for $n\ge 2$)

Other numerical invariants

Function	Value	Explanation
clique number	2	As cycle graph $C_n,n=4$: 2 (independent of $n$ for $n\ge 4$) As $K_{m,n},m=n=2$: 2 (independent of $m,n$, follows from being bipartite) As $n$-dimensional hypercube, $n=2$: 2 (independent of $n$)
independence number	2	As cycle graph $C_n,n=4$: greatest integer of $n/2$ equals greatest integer of 4/2 equals 2 As $K_{m,n},m=n=2$: $max\{m,n\}=max\{2,2\}=2$ As $n$-dimensional hypercube, $n=2$: $2^{n-1}=2^{2-1}=2$
chromatic number	2	As cycle graph $C_n,n=4$: 2 (in general, it is 2 for even $n$ and 3 for odd $n$ As $K_{m,n},m=n=2$: 2 (independent of $m,n$, follows from being bipartite) As $n$-dimensional hypercube, $n=2$: 2 (independent of $n$, follows from being bipartite)
radius of a graph	2	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	2	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
odd girth	infinite	As cycle graph $C_n,n=4$: infinite (since $n$ even) As $K_{m,n},m=n=2$: infinite, since bipartite As $n$-dimensional hypercube, $n=2$: infinite, since bipartite
even girth	4	As cycle graph $C_n,n=4$: $n=4$ (since $n$ even) As complete bipartite graph $K_{m,n},m=n=2$: 4 (independent of $m,n$ as long as both are greater than 1) As $n$-dimensional hypercube, $n=2$: 4 (independent of $n$ for $n\ge 2$)
girth of a graph	4	As cycle graph $C_n,n=4$: $n=4$ As complete bipartite graph $K_{m,n},m=n=2$: 4 (independent of $m,n$ as long as both are greater than 1) As $n$-dimensional hypercube, $n=2$: 4 (independent of $n$ for $n\ge 2$)

Graph properties

Property	Satisfied?	Explanation
connected graph	Yes
regular graph	Yes	all vertices have degree two
vertex-transitive graph	Yes
cubic graph	No
edge-transitive graph	Yes
symmetric graph	Yes
distance-transitive graph	Yes
bridgeless graph	Yes
strongly regular graph	Yes	The graph is a $\mathrm{s}\mathrm{r}\mathrm{g}(4,2,0,2)$
bipartite graph	Yes

Graph operations

Operation	Graph obtained as a result of the operation
complement of a graph	matching graph on 4 vertices
line graph	isomorphic to the original graph
prism of a graph	cube graph

Algebraic theory

The adjacency matrix is:

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

This matrix is uniquely defined up to conjugation by permutations. Below are some important associated algebraic invariants:

Algebraic invariant	Value	Explanation
characteristic polynomial	$t^4-4t^2$
minimal polynomial	$t^3-4t$
rank of adjacency matrix	2
eigenvalues (roots of characteristic polynomial)	0 (multiplicity 2), 2, -2	We can compute these eigenvalues directly using the fact that the graph is a $\mathrm{s}\mathrm{r}\mathrm{g}(4,2,0,2)$

Realization

As Cayley graph

Note that for this to be the Cayley graph of a group, the group must have order 4, and the generating set with respect to which we construct the Cayley graph must be a symmetric subset of the group of size 2.

Group	Choice of symmetric set that is a generating set for which the Cayley graph is this
cyclic group:Z4	cyclic generator and its inverse
Klein four-group	two distinct elements of order two