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

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?

• For triangle free graphs the adjacency matrix may easily have large rank. Say, consider the long cycle. – Fedor Petrov Dec 20 '18 at 8:56
• @FedorPetrov shame on me; I will have to edit my question to make it non-trivial. – Manfred Weis Dec 20 '18 at 9:21

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.