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.$