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.


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.

A faithful homomorphism that is not full.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.