A homomorphism between directed graphs is a function that maps vertices and edges from a source graph to a target graph, preserving the directionality and structure of the edges. Formally, let $G$ and $H$ be directed graphs. A homomorphism $f$ from $G$ to $H$ is a function that assigns:
- a vertex $f(v)$ in $H$ for each vertex $v$ in $G$
- an edge $f(e)$ in $H$ for each edge $e$ in $G$
- Such that $f$ preserves the directionality and structure of edges.
Specifically, for any edge $(u, v)$ in $G$, the corresponding edge $(f(u), f(v))$ in $H$ must also exist and have the same directionality as $(u, v)$.
Homomorphisms are useful for analyzing directed graphs and identifying relationships between graphs by way of the se mappings.
Let $G$ be a directed graph, let $\vec{P}_{n}$ denote the directed path on $n$ nodes, and let $\vec{K}_{n}$ denote the complete graph on $\{1,2, \ldots, n\}$ in which every edge is oriented from the node with lower label to the node with larger label (transitive tournament).
Question:
Prove that $G$ has a homomorphism into $\vec{K}_{n}$ if and only if $\vec{P}_{n+1}$ has no homomorphism into $G$.
My attempt: Let $G = (V, E)$ and $H = (W, F)$ be two directed graphs. A homomorphism from $G$ to $H$ is a function $f: V \rightarrow W$ such that for every edge $(u,v) \in E$, $(f(u), f(v)) \in F$. In other words, a homomorphism preserves the orientation of the edges.
$(\Rightarrow)$
Assume that $G$ has a homomorphism $f: G \rightarrow \vec{K}_n$. We prove that $\vec{P}_{n+1}$ has no homomorphism into $G$.
Suppose, for the sake of contradiction, that there exists a homomorphism $g: \vec{P}_{n+1} \rightarrow G$. We will derive a contradiction by constructing a homomorphism $h: \vec{K}n \rightarrow \vec{P}_{n+1}$ that is not compatible with $f$.
Let $h(i) = i$ for all $i \in {1, 2, \ldots, n}$. For $i < j$, let $(h(i), h(j))$ be the edge in $\vec{P}_{n+1}$, i.e., $h$ preserves the orientation of the edges. It is easy to verify that $h$ is a homomorphism from $\vec{K}_n$ to $\vec{P}_{n+1}$.
Now consider the composition $f \circ g: \vec{P}_{n+1} \rightarrow \vec{K}_n$. Since $f$ and $g$ are both homomorphisms, their composition is also a homomorphism. However, $h$ and $f \circ g$ are not compatible, because for any $i < j$, we have $(h(i), h(j)) \in E(\vec{P}_{n+1})$ but $(f \circ g)(h(i), h(j)) \notin E(\vec{K}_n)$, because $(h(i), h(j))$ is not an edge in $\vec{K}_n$. Therefore, we have a contradiction.
$(\Leftarrow)$
Prove the contrapositive of the statement. If $G$ does not have a homomorphism into $\vec{K}_n$, then $\vec{P}_{n+1}$ cannot have a homomorphism into $G$.
Suppose $G$ does not have a homomorphism into $\vec{K}_n$. Assume for contradiction that there exists a homomorphism $f:\vec{P}_{n+1} \to G$. Let $v_1, v_2, \dots, v{n+1}$ be the vertices of $\vec{P}_{n+1}$, where $v_1$ is the initial vertex and $v{n+1}$ is the terminal vertex. We know that $f(v_i) \neq f(v_j)$ for all $i < j$, since otherwise we would have a directed cycle in $G$.
Since $f(v_1), f(v_2), \dots, f(v_n)$ are pairwise distinct, they induce a subgraph of $G$ that is isomorphic to $\vec{K}_n$, as every pair of distinct vertices is connected by a directed edge. Therefore, $G$ contains a subgraph isomorphic to $\vec{K}_n$, contradicting the assumption that $G$ does not have a homomorphism into $\vec{K}_n$. Hence, if $G$ does not have a homomorphism into $\vec{K}_n$, then $\vec{P}_{n+1}$ cannot have a homomorphism into $G$.
Is there a kind soul who can correct me.
Thank's