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

  • $\begingroup$ 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! $\endgroup$
    – chowching
    Jan 29 '15 at 15:37
  • $\begingroup$ Its not necessarily the union. Take $G = H$ to be the Petersen graph. Then $Aut(G\cup H)$ only has 1 orbit. $\endgroup$
    – Jernej
    Jan 29 '15 at 15:47
  • $\begingroup$ 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. $\endgroup$
    – Jernej
    Jan 29 '15 at 15:51
  • $\begingroup$ 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)$. $\endgroup$
    – chowching
    Jan 29 '15 at 16:03
  • $\begingroup$ I am taking $G$ and $H$ to be non-isomorphic with same degree and size. $\endgroup$
    – chowching
    Jan 29 '15 at 16:28

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.