Proof Paths are Preserved

92 Views Asked by At

I am trying to prove that for graphs $G$ and $H$ with an isomorphism existing from $G$ to $H$, $p$ is a path in $G$ from $u$ to $v$ if, and only if, $f(p)$ is a path in $H$ from $f(u)$ to $f(v)$. My textbooks proof is as follows:

Let $P_n$ be the graph denoted by $V(P_n):=\{1,2,...,n\}$ and $E(P_n):=\{e_1,e_2,...,e_n\}$ where for each $i \in \mathbb{N} , e_i = \{i,i+1\}$.

We have that:

p is a path in $G [1]$ $\iff p \cong P_n [2]$ $\iff f(p) \cong f(P_n) [3]$ $\iff f(p) \cong P_n [4]$ $\iff f(p)$ is a path in $H [5]$

I’m not sure I understand how to get from step [2] to [3], and from step [3] to [4] in either direction. Could someone please elaborate on why this is the case?

1

There are 1 best solutions below

2
On

Having a path in $G$ - a subgraph isomorphic to $P_n$ for some $n$ - means that there is an injective function $p: V(P_n) \to V(G)$ such that for all edges $e = \{i,i+1\} \in E(P_n)$, $p(e) = \{p(i), p(i+1)\} \in E(G)$. If you like (and apparently your textbook does like), we can define this function $p$ to be the path.

Then $f \circ p$ is a function $V(P_n) \to V(H)$ with the same property (because $f$ preserves edges) and therefore $f \circ p$ is a path in $H$.

Conversely, because $f$ also preserves non-edges, if $f \circ p$ is a path in $H$, then $p$ must be a path in $G$.


On the other hand, I really can't get behind some of the notational choices in your textbook's proof:

  • If $p$ is a function, then $p \cong P_n$ doesn't make any sense, because $P_n$ is a graph and $p$ is not a graph.
  • Both $f(p)$ and $f(P_n)$ don't make any sense, because $f$ is a function on vertices. I would accept applying $f$ to a set of vertices, elementwise, but a graph is more than that.