2
$\begingroup$

Let G be a connected graph with n vertices and m edges.

What will be the number of edges after we copy all the vertices , when with copy, I mean a new vertex that connects with the copied vertex and all the other vertices that the copied vertex connects to.

Example: Before Copying After copying

$\endgroup$
6
  • $\begingroup$ *vertex, not vertice $\endgroup$ – Yash Jain Jan 28 '18 at 20:55
  • $\begingroup$ It's clearly $2m+n$. Can you see why? $\endgroup$ – Dan Rust Jan 28 '18 at 20:58
  • $\begingroup$ That's what i thought initially but it's not correct because after the first vertex is coppied and connected to other vertices the degree of the other vertices that this vertex connected to, will increase! $\endgroup$ – Prog Kid Jan 28 '18 at 21:06
  • 1
    $\begingroup$ But surely the new vertices are not connected one by one iteratively. Is it not all done at once? Please define the new graph more concretely. $\endgroup$ – Dan Rust Jan 28 '18 at 21:31
  • $\begingroup$ u're right im updating the description with an example $\endgroup$ – Prog Kid Jan 28 '18 at 21:38
1
$\begingroup$

For a simple graph every edge has become $4$. As an example, you started with an edge $AB$ and now you have $AB, A'B, AB', A'B'$. In addition you have all the edges between the matching vertices like $AA'$. The total is $4m+n$. This does not work if any of your edges are loops.

$\endgroup$
2
  • $\begingroup$ I found out that it might be $4m+n$ but giving a particular example is not as same as proving. I think you should prove the argument "For a simple graph every edge has become $4$". $\endgroup$ – ArsenBerk Jan 28 '18 at 21:56
  • $\begingroup$ @ArsenBerk: this is definitely just a sketch, but it shows the way to go. Take every edge in the original graph, consider the two vertices it joins, there are two pairs of vertices in the duplicated graph, resulting in four edges. $\endgroup$ – Ross Millikan Jan 28 '18 at 23:41
1
$\begingroup$

Ok, it looks like your description isn't quite right from the example you gave. I think maybe you mean, if $G=(V = \{v_1,\ldots, v_k\},E\subset V \times V)$, then $G'=(V',E')$ where $V' = V \cup \{v_1',\ldots,v_k'\}$ and $$E' = \{(v_i,v_j) \mid (v_i,v_j) \in E\} \cup \{(v_i,v_j'), (v_i',v_j) \mid i < j, (v_i,v_j) \in E\}$$ $$\cup \{(v_i',v_j') \mid (v_i,v_j) \in E\} \cup \{(v_i,v_i') \mid v_i \in V\}.$$

I think, from this description, you can probably work out how many edges there are, so I'll leave that to you.

$\endgroup$

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.