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.

  • $\begingroup$ You'll have to clarify your notations. Is A thr adjacency matrix? And what is the definition for $*u$ and $u*$? $\endgroup$ Oct 2 '19 at 8:45
  • $\begingroup$ 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)$. $\endgroup$ Oct 2 '19 at 9:20
  • $\begingroup$ Two vertices at distance at least $3$. $\endgroup$
    – dEmigOd
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.