# Is composition of isomorphism and complementation of a graph commutative?

Composition of two functions, $${f_1}$$ and $${f_2}$$, is commutative if $${f_1} \circ {f_2} = {f_2} \circ {f_1}$$. Even when the functions are bijective, it is not necessary that their composition is commutative. My question is, given two specific bijective functions, isomorphism and complementation on a graph $$G$$, is their composition commutative?

I realized that if two graphs $$G$$ and $$H$$ are isomorphic, then their complements are also isomorphic. This led me to see (ref below proof by contradiction) that the above composition is commutative. Can anyone pls tell me if this is correct! It would be great if you could point out any other theory that has led to similar conclusion.

My reasoning: By contradiction, $${f_1} \circ {f_2} (G) \not= {f_2} \circ {f_1} (G)$$.

$$=> {f_1} ({f_2}(G))={f_1} (G^{c}) \not= {f_2} ({f_1} (G))= {f_2} (H) = H^{c}$$
However, $$H^{c}$$ and $$G^{c}$$ are isomorphic.

• I think not, take for example a graph G and a graph H, which is equal to G with one more distinct vertex w (no edges between w to the other vertices). Commented Oct 3, 2019 at 9:09
• @friedvir - In that case, are G and H isomorphic! Commented Oct 3, 2019 at 9:33
• Sorry didn't notice, then i guess you are right, just need the explanation for why the complement graphs are isomorphic, won't be hard to prove Commented Oct 3, 2019 at 9:44
• I don't understand what is meant by "the function represents complementation". What are the domain and range of the function $f_2$ (vertex sets? edge sets?) and how does it act?
– bof
Commented Oct 7, 2019 at 5:59
• I understand perfectly well what the complement of a graph is, but I don't know what function you are talking about. For instance, if $G$ has vertex set $V=\{w,x,y,z\}$ and edge set $E=\{wx,xy,yz,wz\}$, then $G^c$ has vertex set $\{w,x,y,z\}$ and edge set $\{wy,xz\}$. But what is the function $f_2:G\to G^c$ that you are talking about? What is $f_2(w)$? Is $f_2$ just the identity map on $V$?
– bof
Commented Oct 7, 2019 at 6:31

If $$G$$ and $$H$$ are finite simple graphs and $$\varphi: G \rightarrow H$$ is a graph isomorphism then $$\varphi(G)^C = \varphi(G^C)$$ because these two graphs have the vertices and the same edges. So you could say that complementation and applying the isomorphism commute.