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:

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

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
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:

${\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&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	Fill this in later
minimal polynomial	Fill this in later
rank of adjacency matrix	2
eigenvalues (roots of characteristic polynomial)