I am stuck on this problem. It is about a simple, undirected and connected graph G on N nodes. It says to consider two vertices u and v s.t.
- A(u,v) = 0 (with A being the adjacency matrix for G)
- $$\sum_{z=1}^{n} A(u,z)A(v,z) = 0$$
As for the first condition I know it means that there is no edge between u and v. But as for the second, does it mean that there are no edges in general linking both u and v to the same node z?
It then says to consider the graph G’ on N – 1 nodes obtained from G by merging u and v in a single node. It wants me to show that G’ is also a simple, undirected and connected graph.
Best Answer
Since every $A_{i,j}$ is either 0 or 1, the second condition amounts to say that for all $z$, $A_{u,z}A_{v,z} = 0$, ie there is no vertex $w\in V$ such that both $u$ and $v$ are both connected to $w$.
Say $G$ has vertices $V$ and edges $E$.
For the graph $G'$, we have $G' = (V',E')$ where : $$V' = V \setminus\{v\}$$ $$ E' = \{(a,b)\in E \big| \ a\neq v\} \sqcup \{(u,b) \big| \ (v,b) \in E\}$$
Your first condition ($A_{u,v} = 0$) implies that $(u,u) \notin E'$.
Your second condition implies that you don't have a double edge from $u$ to any vertex.
Hence, $G'$ is simple.