Proof that using adjacency matrix for bipartite testing has Ω(n^2)

Question

so in one of my lectures I came across the proof for:

𝐓𝐡𝐞𝐨𝐫𝐞𝐦: 𝐴𝑛𝑦 algorithm that determines if a graph is bipartite that has as its input an undirected graph 𝐺 = (𝑉, 𝐸) represented as an 𝑛 × 𝑛 adjacency matrix, has the running time of Ω(𝑛^2)

We assume an algorithm ALG which test for bipartiteness (returns either true or false). And we also assume we have a graph 𝐺0 = (𝑉, 𝐸0) with 𝑉 = {1,2, … , 𝑛} and 𝐸0 = { 1, 𝑖 : 2 ≤ 𝑖 ≤ 𝑛} (as this is a star it is a bipartite graph)

Within the proof there's a step saying: "For a given algorithm ALG, we will construct another graph 𝐺1 st: if ALG performs less than (𝑛−1)C2 accesses to the adjacency matrix 𝐴 of 𝐺0, then ALG will not distinguish between 𝐺0 and 𝐺1, and 𝐺1 is not bipartite."

My question is what does (n-1)C2 accesses mean. Is it saying that for example if we have a different V = {A,B,C,D} then ALG will look at all node pairs except for the ones between D and the other nodes ?

Sorry if this isn't clear this proof really confused me.

Answer 1

G₀ is an n-vertex star graph. It's bipartite, but if you add any other edge to it, the resulting graph is not. There are n−1 choose 2 = (n−1)(n−2)/2 = Ω(n²) other edges that we can add. Every correct algorithm must check every single one in order to verify that G₀ is bipartite.