A general proof for proving paths are shared in isomorphic graphs.

504 Views Asked by At

The question is

Let $G_1$ = ($V_1$, $E_1$) and $G_2$ = ($V_2$, $E_2$) be isomorphic via the function f : $V_1$ $\to$ $V_2$. Prove that if $v_1$, $v_2$, ... , $v_k$, is a path in $G_1$ then f($v_1$), f($v_2$), ... , f($v_k$), is a path in $G_2$.

I understand the question, that if a path exists in $G_1$ then prove it must exist in $G_2$. But I was not given two graphs to help with so I need a general proof, I just have absolutely no idea how to develop one.

The answer I have as of now, which I do not believe is correct:

Assume $G_1$ and $G_2$ are isomorphic.

If $G_1$ and $G_2$ are isomorphic then we have the bijective function f : $V_1$ $\to$ $V_2$.

Since we have the function f : $V_1$ $\to$ $V_2$ then we can pull any sequence of vertices we want out of $V_2$ by inputting a sequence from $V_1$.

1

There are 1 best solutions below

0
On

A graph isomorphism preserves adjacencies. If $u,v\in V(G_1)$ are adjacent in $G_1$ then $f(u),f(v)\in V(G_2)$ are adjacent in $G_2$. Simply apply this idea to each edge in your path in $G_1$ to find the path in $G_2$.