# What is the difference between a full and a faithful graph homomorphism?

In their paper "Graph homomorphisms: structure and symmetry" Gena Hahn and Claude Tardif introduce the subject of graph homomorphism "in the mixed form of a course and a survey".

Let $$G$$ and $$H$$ be [simple] graphs. A function $$\phi : V (G) \longrightarrow V (H)$$ is a homomorphism from $$G$$ to $$H$$ if it preserves edges, that is, if for any edge $$[u,v]$$ of $$G$$, $$[\phi(u),\phi(v)]$$ is an edge of $$H$$. We write simply $$\phi : G \longrightarrow H$$.

[...]

A homomorphism $$\phi : G \rightarrow H$$ is called faithful if $$\phi(G)$$ is an induced subgraph of $$H$$. It will be called full if $$[u,v] \in E(G)$$ if and only if $$[\phi(u),\phi(v)] \in E(H)$$, that is, when $$\phi^{-1}(x) \cup \phi^{-1}(y)$$ induces a complete bipartite graph whenever $$[x,y] \in E(H)$$.

In other words, a homomorphism $$\phi : G \rightarrow H$$ is faithful when there is an edge between any two pre-images $$\phi^{-1}(u)$$ and $$\phi^{-1}(v)$$ such that $$[u,v]$$ is an edge of $$H$$. When a faithful homomorphism $$\phi$$ is bijective, it is full since each $$\phi^{-1}(u)$$ is a singleton, and we have that $$[\phi^{-1}(u),\phi^{-1}(v)]$$ is an edge in $$G$$ if and only if $$[u,v]$$ is an edge in $$H$$.

I'm having some difficulties with these definitions, insofar that I don't really get the difference, my intuitive understanding tells me its the same.

I think that a full homomorphism is always faithful, is that correct? Can you give an example of a non full, but faithful homomorphism? Additional imagery would be very kind.

Sidenote: I'm wondering how to generalize these definitions to non simple graphs and am certain that this had been done before, regarding this please see my literature request.

## 1 Answer

Let $\phi:G\rightarrow H$ be a homomorphism and consider every pair of $X=\phi^{-1}(u)$ and $Y=\phi^{-1}(v)$ where $u$ and $v$ are adjacent vertices of $H$. $\phi$ is faithful if and only if for all such $(X,Y)$, there exist $x\in X$ and $y\in Y$ such that $x$ and $y$ are adjacent. $\phi$ is full if and only if for all such $(X,Y)$, for all $x\in X$ and $y\in Y$, $x$ and $y$ are adjacent. So a full homomorphism is always faithful, but the converse fails.

For example, consider the depicted homomorphism $\phi$ from a graph $G$ of order $6$ to a graph $H$ of order $3$. The circled groups of vertices $X$, $Y$, and $Z$ are the pre-images of the vertices $u$, $v$, and $w$, respectively. The edges of $H$ are $uv$ and $vw$, so because $G$ has edges between the corresponding pre-image pairs of $(X,Y)$ and $(Y,Z)$, $\phi$ is faithful. For $\phi$ to be full, these pairs should induce complete bipartite graphs. This is true for the pair $(X,Y)$, but not for $(Y,Z)$ because $yz_2$ is not an edge of $G$, so $\phi$ is not full. 