# How would you define this conditions on a simple undirected and connected graph?

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.

• You'll have to clarify your notations. Is A thr adjacency matrix? And what is the definition for $*u$ and $u*$? Oct 2 '19 at 8:45
• You should use subscripts to denote elements of the matrix $A$ : write $A_{u,v}$ (latex is A_{u,v} ) rather than $A(u,v)$. Oct 2 '19 at 9:20
• Two vertices at distance at least $3$. Oct 2 '19 at 9:21

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.