# Adding an edge and a vertex to non-isomorphic graphs

Let $G$ and $H$ be two non-isomorphic simple graphs of equal order and equal size.

Suppose I am to add a vertex $v$ and and edge $e$ incident to $v$ to $G$ and $H$. By add I mean to connect $v$ to another vertex $u$ in $G$ or $H$ so that $uv=e$.

Is it true that I can do this in such a way that $G\cup\{v\}\cup\{e\} \ncong H\cup\{v\}\cup\{e\}$?

Clearly if I just have $G\cup\{v\}$ and $H\cup\{v\}$ then the two are not isomorphic. Since $G$ and $H$ are not isomorphic I can find a property that only holds to one of them. For example there might be a vertex in $G$ and a vertex in $H$ with different degrees. Intuitively I just have to connect vertex $v$ so that the said property is preserved. Now how do I prove that I can always do that?

Also, what if have to do it the other way around? Same conditions as above but this time instead of adding a vertex I will be deleting a vertex and all the edges incident to it. Can I always choose a vertex from each graph whose removal will result to non-isomorphic graphs with the same order and size?

Thank you!

For the first problem you can do as follows. Compute the orbits of $\rm{Aut}(G \cup H).$

Since the graphs are not isomorphic there is more than one orbit and you can pick two distinct orbits $o,o'$ such that a vertex $v \in V(G)$ is in $o$ and a vertex $u \in V(H)$ is in $o'.$

This then give you the neighbors of the added vertices that you need to add to $G$ and $H$ respectively.

For the other direction you can do the same thing - that is given non isomorphic graphs $G$ and $H$ you removed vertices $v$ and $u$ with the property described above.

Note. If this is not direct enough you can think of the orbits of $\rm{Aut}(G)$ of a graph $G$ as a partition of $V(G)$ so that $u,v$ are in the same orbit iff $G-u$ is isomorphic to $G-v.$

• Am I correct in my understanding that the orbit of $Aut(G\cup H)$ is the same as the union of the orbits of $Aut(A)$ and $Aut(B)$? So I can always find a $v\in V(G)$ in $o$ and a vertex $u\in V(H)$ in $o'$. But I should also have that $|o|=|o'|$ otherwise the new non-isomorphic graphs will not have the same size. Can I always find two such orbits? Thank you! Jan 29 '15 at 15:37
• Its not necessarily the union. Take $G = H$ to be the Petersen graph. Then $Aut(G\cup H)$ only has 1 orbit. Jan 29 '15 at 15:47
• Intuitively, two vertices are in the same orbit if they are "indistinguishable" in other words any isomorphism from $G$ to $H$ only can map a vertex to vertices in the same orbit. Jan 29 '15 at 15:51
• Oh sorry. I was referring to $G$ and $H$ non-isomorphic. The way I see it, if $v\in V(G)$ is in an orbit $o$ of $Aut(G\cup H)$ then a vertex $u\in V(H)$ cannot be in $o'$ because otherwise $G\cup H-\{v\}\cong G\cup H-\{u\}$ but $G\cup H-\{v\}=(G-\{v\})\cup H$ and $G\cup H-\{u\}=G\cup (H-\{u\})$ and these would imply that $G$ and $H$ must be isomorphic. Which is not. Thus the orbits of $Aut(G\cup H)$ must just be the union of the orbits of $Aut(G)$ and $Aut(H)$. Jan 29 '15 at 16:03
• I am taking $G$ and $H$ to be non-isomorphic with same degree and size. Jan 29 '15 at 16:28