Complete bipartite graph:K3,3

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 as the complete bipartite graph $K_{3,3}$. Explicitly, it is a graph on six vertices divided into two subsets of size three each, with edges joining every vertex in one subset to every vertex in the other subset.

The graph is also known as the utility graph. The name arises from a real-world problem that involves connecting three utilities to three buildings. The problen is modeled using this graph.

Explicit descriptions

Descriptions of vertex set and edge set

We provide a description where the vertex set is $\{1,2,3,4,5,6\}$ and the two parts are $\{1,2,3\}$ and $\{4,5,6\}$:

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

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

Adjacency matrix

With the above ordering of the vertices, the adjacency matrix is as follows:

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

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	6	As $K_{m,n},m=n=3$: $m+n=3+3=6$
size of edge set	9	As $K_{m,n},m=n=3$: $mn=(3)(3)=9$

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	3	As $K_{m,n},m=n=3$: Since $m,n$ are equal, the graph is vertex-transitive and $(m=n)$-regular, so we get $m=n=3$
eccentricity of a vertex	2	As $K_{m,n},m=n=3$: 3 (independent of $m,n$, though it uses that both numbers are greater than 1)

Other numerical invariants

Function	Value	Explanation
clique number	2	As $K_{m,n},m=n=3$: 2 (independent of $m,n$, follows from being bipartite)
independence number	3	As $K_{m,n},m=n=3$: $max\{m,n\}=max\{3,3\}=3$
chromatic number	2	As $K_{m,n},m=n=3$: 2 (independent of $m,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 $K_{m,n},m=n=3$: infinite, since bipartite As $n$-dimensional hypercube, $n=3$: infinite, since bipartite
even girth	4	As $K_{m,n},m=n=3$: 4 (independent of $m,n$ as long as both are greater than 1)
girth of a graph	4	As$K_{m,n},m=n=3$: 4 (independent of $m,n$ as long as both are greater than 1)

Graph properties

Property	Satisfied?	Explanation
connected graph	Yes
regular graph	Yes	$K_{m,n}$ is regular if $m=n$
vertex-transitive graph	Yes	$K_{m,n}$ is vertex-transitive if $m=n$
cubic graph	Yes
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}(6,3,0,3)$. In general, a complete bipartite graph $K_{m,n}$ is strongly regular iff $m=n$, and in that case it is a $\mathrm{s}\mathrm{r}\mathrm{g}(2m,m,0,m)$
bipartite graph	Yes	By definition of complete bipartite graph

Algebraic theory

Adjacency matrix

The adjacency matrix is as follows:

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

Laplacian matrix

The Laplacian matrix is as follows:

$\left(\begin{array}{cccccc}3& 0& 0& -1& -1& -1\\ 0& 3& 0& -1& -1& -1\\ 0& 0& 3& -1& -1& -1\\ -1& -1& -1& 3& 0& 0\\ -1& -1& -1& 0& 3& 0\\ -1& -1& -1& 0& 0& 3\\ \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-6)(t-3{)}^4$	As complete bipartite graph $K_{m,n},m=n=3$: $t(t-(m+n))(t-m{)}^{n-1}(t-n{)}^{m-1}$
minimal polynomial	$t(t-3)(t-6)$	As complete bipartite graph $K_{m,m},m=3$: $t(t-m)(t-2m)$
rank of Laplacian matrix	5	As complete bipartite graph $K_{m,n},m=n=3$: $m+n-1=3+3-1=5$
eigenvalues (roots of characteristic polynomial)	0 (1 time), 6 (1 time), 3 (4 times)	As complete bipartite graph $K_{m,n},m=n=3$: 0 (1 time), $m+n=6$ (1 time), $m=n=3$ (4 times: $n-1=3-1=2$ times as $m$ and $m-1=3-1=2$ times as $n$)

Normalized Laplacian matrix

The normalized Laplacian matrix is as follows:

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