Classifying Simple Graphs with Rank 2 and 3

Question

I asked to classify simple graphs with adjacency matrices of rank $2$ or $3$. It is easy to see when the number of vertices is $2$ and $3$ that the only such graphs are $K_2$ and $K_3$. However, I do not know how to classify graphs with rank $2$ and $3$ in general.

I am studying algebraic graph theory from Algebraic Graph Theory by Biggs but haven't progressed much in the book.

Answer 1

Thanks to Misha Lavrov - he noticed my mistake.

Hints for the case when the rank is $2$.

1. It is sufficient to describe graphs without isolated vertices.

2. The adjacency matrix of each complete bipartite graph has rank $2$. If $\{v_1,\ldots,v_s\}$ and $\{v_{s+1},\ldots,v_n\}$ ($n>s\geq1$) are his parts, then the adjacency matrix of such graph has the form $$ \begin{pmatrix} 0&0&\ldots&0&1&\ldots&1\\ 0&0&\ldots&0&1&\ldots&1\\ \ldots &\ldots &\ldots &\ldots &\ldots &\ldots &\ldots\\ 0&0&\ldots&0&1&\ldots&1\\ 1&1&\ldots&1&0&\ldots&0\\ \ldots &\ldots &\ldots &\ldots &\ldots &\ldots &\ldots\\ 1&1&\ldots&1&0&\ldots&0\\ \end{pmatrix}, $$ where the upper block of zeros has dimensions $s\times s$.

3. Reverse. Let $G$ be a graph. Call the rank of graph $G$ the rank of an adjacency matrix of $G$. If $G$ has no isolated vertices and is not connected, then $\operatorname{rank}(G)\geq4$.

4. If $uv$ and $xy$ are edges of $G$ and $u$ is not adjacent to both $x$ and $y$, then $\operatorname{rank}(G)\geq4$. Let us number the vertices of graph $G$ such that $x_1=u$, $x_2=v$, $x_3=x$, $x_4=y$. The first four rows of an adjacency matrix of graph $G$ have the form: $$ \begin{pmatrix} 0&1&0&0&*&\ldots&*\\ 1&0&*&*&*&\ldots&*\\ 0&*&0&1&*&\ldots&*\\ 0&*&1&0&*&\ldots&*\\ \end{pmatrix}. $$ We see that the minor in the first four columns equals $1$.

5. Similarly it is proved that if graph $G$ has triangle, then the rank of $G$ is at least $3$.

6. Let $G$ be a connected graph of rank $2$ and $v\in V(G)$. Let $W=N_G(v)$ be neighbors of vertex $v$. Let $U=V(G)\setminus W$. It follows from 5 that $W$ is an independent set. It follows from 4 that $U$ is an independent set and each vertex of $U$ is connected with each vertex of $W$. If $|W|=m$, $|U|=n$, then $G=K_{m,n}$.

For the case when the rank is equal to 3. Compute the rank of the adjacency matrix of such a graph:

Supplement.

Another approach could be purely algebraic. Briefly, it is as follows.

I. Let $G$ be a rank 2 graph with no isolated vertices and let $x$ and $y$ form a basis of the rows of an adjacency matrix $A$ of $G$. Let $$ x=(\alpha_1,\alpha_2,\ldots,\alpha_n), y=(\beta_1,\beta_2,\ldots,\beta_n). $$ It is not difficult to see that

1. $\alpha_i+\beta_i =1$ for any $i$ y
2. Every row of $A$ coincides with either $x$ or $y$.
3. Hence we conclude that the vertices $x$ and $y$ are adjacent and graph $G$ is a complete bipartite graph.

II. The case when the rank of $G$ is $3$. Just the basic steps:

1. If the graph $G$ is connected and the rank of $G$ is $3$, then $G$ has triangles.

2. Choose three rows $x,y,z$ that form the basis of rows of the adjacency matrix $A$ of $G$. We can assume that the vertices $x,y,z$ form a triangle. (We denote the vertices and their corresponding rows $A$ by the same symbol.)

3. Every row of $A$ coincides with either $x$ or $y$ or $z$.

4. Hence we conclude that graph $G$ is the complete tripartite graph.

Note 1. I'm a little confused by the term rank of a graph. The fact is that in the literature it is understood as a variety of things. Here the rank of a graph means the rank of its adjacency matrix.

Note 2. The given classification in the case of rank $3$ is also a bit confusing. It is possible that I am wrong. I will try to prepare a detailed description of each step.

Supplement 2.

Proof II.1.

Suppose the graph $G$ has no triangles.

(i) If $x_1,x_2,x_3,x_4$ is a path in $G$, then the vertices $x_1$ and $x_4$ are adjacent.

If they are not, write out the first 4 rows of the adjacency matrix $G$. Choose the numbering of vertices of $G$ so that $x_i$ is the first. $$ \begin{pmatrix} 0&1&0&0&*&\ldots&*\\ 1&0&1&0&*&\ldots&*\\ 0&1&0&1&*&\ldots&*\\ 0&0&1&0&*&\ldots&*\\ \end{pmatrix}. $$ We see that $\operatorname{rank}(G)\geq4$.

(ii) The graph $G$ is bipartite.

For this it is sufficient to prove that $G$ has no cycles of odd length. If $x_1,\ldots,x_s$ is the shortest cycle of odd length, then $s\geq5$ and according to (i) $x_1$ and $x_4$ are adjacent. But then the cycle $x_1,x_4,\ldots,x_s$ has length $s-2<s$.

(iii) Let us prove that $G$ is a complete bipartite graph.

Let $U$ and $W$ be parts of graph $G$. Let there exist two non-adjacent vertices $x\in U,y\in W$.
Since the graph $G$ is connected, there exist paths connecting $x$ and $y$. Choose a shortest path among them: $x=x_1,y_1,x_2,y_2,\ldots,x_r,y_r=y$ where $x_1,\ldots,x_r\in U$, $y_1,\ldots,y_r\in W$ and $r\geq2$. If $r>2$, then by (i) $x$ and $y_2$ are adjacent and hence the path $x=x_1,y_2,\ldots,x_r,y_r=y$ is shorter.

(iv) As we know a complete bipartite graph has rank $2$. This contradicts the condition that $\operatorname{rank}(G)=3$.

Proof II.2.

Choose the numbering of vertices of $G$ so that $x,y,z$ is the first: $$A= \begin{pmatrix} 0&1&1&*&\ldots&*\\ 1&0&1&*&\ldots&*\\ 1&1&0&*&\ldots&*\\ \alpha_1&\alpha_2&\alpha_3&*&\ldots&*\\ \ldots&\ldots&\ldots&\ldots&\ldots& \end{pmatrix}. $$ We see that the first three rows of $A$ are linearly independent and hence the basis of the rows of $A$.

Proof II.3.

Let $v=(\alpha_1,\alpha_2,\alpha_3,\ldots)$ be some row of the matrix $A$. We have $$ v=\alpha x+\beta y+\gamma z. $$ Consider four cases:

(1) $\alpha_1=\alpha_2=\alpha_3=0\Rightarrow \alpha=\beta=\gamma=0\Rightarrow v=0$. This is impossible since $G$ has no isolated vertices.

(2) Among $\alpha_1,\alpha_2,\alpha_3$ exactly two numbers are $0$. We can assume that $\alpha_1=\alpha_2=0$ and $\alpha_3=1$. So $\alpha=1/2$, $\beta=1/2$, $\gamma=-1/2$. This is also impossible because otherwise in the corresponding column of the matrix $A$ the first three entries are equal to $0,0,1$ and we obtain that $\alpha\cdot0+\beta\cdot0+\gamma\cdot1=-1/2$.

(3) Among $\alpha_1,\alpha_2,\alpha_3$ there is exactly single number equal to $0$. We can assume that $\alpha_1=0$ and $\alpha_2=\alpha_3=1$. So $\alpha=1$, $\beta=0$, $\gamma=0$. Hence $v=x$.

(4) $\alpha_1=\alpha_2=\alpha_3=1\Rightarrow \alpha=\beta=\gamma=1/2$. This is impossible because otherwise in the corresponding column of the matrix $A$ the first three entries are equal to $1,1,1$ and we obtain that $\alpha\cdot1+\beta\cdot1+\gamma\cdot1=3/2$.

We see that any row of the matrix $A$ is equal to one of the rows $x,y,z$.

Note 3. Since the matrix $A$ is symmetric, the same reasoning shows that there are exactly two $1$s among the first three occurrences of each column of the matrix $A$. In other words, each vertex of graph $G$ is adjacent to exactly two vertices of $x,y,z$.

Proof II.4.

Let $X$ be the set of all those vertices of graph $G$ whose corresponding rows in $A$ are equal to $x$. Similarly, define $Y$ and $Z$. Clearly, $X,Y,Z$ are independent sets. Let $u\in X$, $v\in Y$. As can be seen from the following scheme, since $u=x$, $v=y$ and among the first three entries of columns $u$ and $v$ there should be exactly two 1s of vertices $u$ and $v$ adjacent. $$ \begin{matrix} & & & u &&& v & \\ x & & & 0 &&& 1 &\\ y & & & 1 &&& 0 &\\ z & & & 1 &&& 1 &\\ &&&&&&&\\ u&&&0&&&1&\\ &&&&&&&\\ v&&&1&&&0&\\ \end{matrix}. $$