TIFR CSE 2021 | Part B | Question: 13

Question

Let $A$ be a $3 \times 6$ matrix with real-valued entries. Matrix $A$ has rank $3$. We construct a graph with $6$ vertices where each vertex represents distinct column in $A$, and there is an edge between two vertices if the two columns represented by the vertices are linearly independent. Which of the following statements $\text{MUST}$ be true of the graph constructed?

• A. Each vertex has degree at most $2$.
• B. The graph is connected.
• C. There is a clique of size $3$.
• D. The graph has a cycle of length $4$.
• E. The graph is $3$-colourable.

Comments

@Deepak Poonia sir, Rank of matrix is 3 so #Linear independent column.

hence we got clique of size 3.

but each vexterx has degree atmost 2 seems it is correct option.

Answer 1

Option C) There is a clique of size 3.

rank of matrix A is 3, Therefore 3 of the columns must be linearly independent of each other, Hence a clique of size 3.

Comments

@Deepak Poonia the graph im getting is $K_{3}$ along with 3 isolated vertex, here clique of size $3$ is present but im getting option $E$ also that it is 3 colourable.

---

@Deepak Poonia could you explain this question