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, called the square 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)$

If we re-ordered the vertices by interchanging the roles of vertices 2 and 3, we would get the following adjacency matrix:

$\left(\begin{array}{cccc}0& 0& 1& 1\\ 0& 0& 1& 1\\ 1& 1& 0& 0\\ 1& 1& 0& 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

Adjacency matrix

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)$

It can alternately be written in the following form, which is more computationally convenient because it clearly identifies blocks of 0s and 1s:

$\left(\begin{array}{cccc}0& 0& 1& 1\\ 0& 0& 1& 1\\ 1& 1& 0& 0\\ 1& 1& 0& 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$	As complete bipartite graph $K_{m,n},m=n=2$: $t^{m+n}-mn{t}^{m+n-2}=t^{2+2}-(2)(2)t^{2+2-2}=t^4-4t^2$
minimal polynomial	$t^3-4t$	As complete bipartite graph $K_{m,n},m=n=2$: $t^3-mnt=t^3-(2)(2)t=t^3-4t$
rank of adjacency matrix	2	As complete bipartite graph $K_{m,n},m=n=2$: 2 (independent of $m,n$)
eigenvalues (roots of characteristic polynomial)	0 (2 times), 2 (1 time), -2 (1 time)	As complete bipartite graph $K_{m,n},m=n=2$: 0 ($m+n-2=2+2-2=2$ times), $\sqrt{mn}=\sqrt{(2)(2)}=2$ (1 time), $-\sqrt{mn}=-\sqrt{(2)(2)}=-2$ (1 time)

Laplacian matrix

The Laplacian matrix is as follows:

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

The matrix is uniquely defined up to permutation by conjugations. Below are some algebraic invariants associated with the matrix:

Algebraic invariant	Value	Explanation
characteristic polynomial	$t(t-4)(t-2{)}^2$	As complete bipartite graph $K_{m,n},m=n=2$: $t(t-(m+n))(t-m{)}^{n-1}(t-n{)}^{m-1}$
minimal polynomial	$t(t-2)(t-4)$	As complete bipartite graph $K_{m,m},m=2$: $t(t-m)(t-2m)$
rank of Laplacian matrix	3	As complete bipartite graph $K_{m,n},m=n=3$: $m+n-1=2+2-1=3$
eigenvalues (roots of characteristic polynomial)	0 (1 time), 4 (1 time), 2 (2 times)	As complete bipartite graph $K_{m,n},m=n=3$: 0 (1 time), $m+n=4$ (1 time), $m=n=2$ (2 times: $n-1=2-1=1$ times as $m$ and $m-1=2-1=1$ times as $m$)

Normalized Laplacian matrix

The normalized Laplacian matrix is as follows:

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

The matrix is uniquely defined up to permutation by conjugations. Below are some algebraic invariants associated with the matrix:

Algebraic invariant	Value	Explanation
characteristic polynomial	$t(t-2)(t-1{)}^2$	As complete bipartite graph $K_{m,n},m=n=2$: $t(t-(m+n)/\sqrt{mn})(t-\sqrt{m/n}{)}^{n-1}(t-\sqrt{n/m}{)}^{m-1}$
minimal polynomial	$t(t-1)(t-2)$	As complete bipartite graph $K_{m,m},m=2$: $t(t-1)(t-2)$
rank of normalized Laplacian matrix	3	As complete bipartite graph $K_{m,n},m=n=2$: $m+n-1=2+2-1=5$
eigenvalues (roots of characteristic polynomial)	0 (1 time), 2 (1 time), 1 (2 times)	As complete bipartite graph $K_{m,n},m=n=3$: 0 (1 time), $(m+n)/\sqrt{mn}=2$ (1 time), 1 (2 times: $n-1=2-1=1$ time as $\sqrt{m/n}$ and $m-1=2-1=1$ time as $\sqrt{n/m}$)

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

Geometric embeddings

Planar embedding as a square

The graph has a very nice embedding as a square in the plane: the vertices embed as the vertices of the square, and the edges as the edges of the square. Explicitly, we can embed the vertices as:

$1\leftrightarrow (0,0),2\leftrightarrow (1,0),3\leftrightarrow (1,1),4\leftrightarrow (0,1)$

This embedding is nice in a number of ways:

• It demonstrates that the graph is a planar graph.
• Moreover, it demonstrates that the graph can be embedded in the plane using straight line segments for edges. This is not possible for all planar graphs.
• It demonstrates that the graph is a unit distance graph: two points are adjacent in the embedding if and only if the distance between them in the Euclidean plane is 1.
• It preserves all the symmetries of the graph. Explicitly, for every automorphism of the cycle graph, there is a (unique) self-isometry of the Euclidean plane that induces that automorphism on the cycle graph.