Estimating Maximal-Clique of Metric Graphs via the Rank of their Adjacency Matrix

Question

Let $\mathrm{M}\in\lbrace0,1\rbrace^n$ be the adjacency matrix of a graph $\mathrm{G}\left(V,E\subseteq\lbrace\lbrace u,v\rbrace| u,v\in V\rbrace\right)$ of order $n$.

Let $\mathrm{G}$ additionally be metric in the sense, that $$\lbrace v_i, v_j, v_k\rbrace\subseteq V\ \ \wedge\ \ w_{uv}\in\lbrace 0,1\rbrace\ \ \wedge\ \ w_{uv}=1\iff e_{uv}\in E$$ $$\implies w_{ij}+w_{jk}+w_{ki}\ \in\ \lbrace 0,2,3\rbrace$$

Question: is it then true that $$\mathrm{rank}(\mathrm{M})=\max_{n'}\mathrm{K}_{n'}\subseteq\mathrm{G}$$ resp. how is the the rank of the adjacency matrix related to the size of the maximal clique?

Answer 1

I also assume that the graph contains at least one edge, else the maximal clique contains 1 vertex while the rank is 0. In any graph (not necessarily metric) which contains at least one edge the rank of the adjacency matrix is not less than the size of maximal clique (look to corresponding minor).

Your metric condition is equivalent to the following: the vertices may be partitioned onto $m$ disjoint non-empty groups $V_1,\dots,V_m$ so that any two vertices from the same $V_i$ are not joined while any two vertices from different $V_i$'s are joined. It implies that the rank of such a matrix is at most $m$, since there are exactly $m$ different rows. On the other hand, the maximal clique size is exactly $m$. Therefore here we have indeed the equality.