Number of edges after we copy all the vertices.

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:

• *vertex, not vertice – Yash Jain Jan 28 '18 at 20:55
• It's clearly $2m+n$. Can you see why? – Dan Rust Jan 28 '18 at 20:58
• 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! – Prog Kid Jan 28 '18 at 21:06
• 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. – Dan Rust Jan 28 '18 at 21:31
• u're right im updating the description with an example – Prog Kid Jan 28 '18 at 21:38

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.
• 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$". – ArsenBerk Jan 28 '18 at 21:56
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\}.$$