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:

${\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\\\end{pmatrix}}$

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

${\begin{pmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\\\end{pmatrix}}$

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\geq 2$)

Other numerical invariants

Function	Value	Explanation
clique number	2	As cycle graph $C_{n},n=4$: 2 (independent of $n$ for $n\geq 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\geq 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\geq 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 $\operatorname {srg} (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:

${\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\\\end{pmatrix}}$

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

${\begin{pmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\\\end{pmatrix}}$

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}-mnt^{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:

${\begin{pmatrix}2&0&-1&-1\\0&2&-1&-1\\-1&-1&2&0\\-1&-1&0&2\\\end{pmatrix}}$

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:

${\begin{pmatrix}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{pmatrix}}$

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-2)(t-1)^{m+n-2}$
minimal polynomial	$t(t-1)(t-2)$	As complete bipartite graph $K_{m,n},m=n=2$: $t(t-1)(t-2)$ (independent of $m,n$ as long as $m+n>2$)
rank of normalized Laplacian matrix	3	As complete bipartite graph $K_{m,n},m=n=2$: $m+n-1=2+2-1=3$
eigenvalues (roots of characteristic polynomial)	0 (1 time), 2 (1 time), 1 (2 times)	As complete bipartite graph $K_{m,n},m=n=2$: 0 (1 time), 2 (1 time), 1 ($m+n-2=2+2-2=2$ times)

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.