Number of edges after we copy all the vertices.

139 Views Asked by At

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

2

There are 2 best solutions below

2
On BEST ANSWER

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.

0
On

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.