# Wikipedia definition of graph homomorphism: is this correct?

Consider the definition of a graph homomorphism given here:

A graph homomorphism $f$ from a graph $G=(V,E)$ to a graph $G'=(V',E')$, written $f:G \rightarrow G'$, is a mapping $f:V \rightarrow V'$ from the vertex set of $G$ to the vertex set of $G'$ such that $\{u,v\}\in E$ implies $\{f(u),f(v)\}\in E'$.

At the beginning the article states "...a graph homomorphism is a mapping between two graphs that respects their structure. ..."

So I was wondering:

Is it a typo or is "implies" really enough?

Shouldn't it be

A graph homomorphism $f$ from a graph $G=(V,E)$ to a graph $G'=(V',E')$, written $f:G \rightarrow G'$, is a mapping $f:V \rightarrow V'$ from the vertex set of $G$ to the vertex set of $G'$ such that $\{u,v\}\in E$ if and only if $\{f(u),f(v)\}\in E'$.?

## 1 Answer

No. You're confusing the concept of isomorphism (with the image) with the concept of homomorphism. You are interpreting the verb "respect" too strictly.

In general, a homomorphism between two algebraic objects with the same kind of structure (e.g. graphs, groups, fields) is a mapping such that its image has the same kind of structure, as a subobject.

On the other hand, an isomorphism between two object means that they have the very same structure or, in other words, that they are indistinguishable by that structure alone.

In other words, observe that it is generally very useful to express the notion of subobject as an injective morphism. Your definition would imply that every subgraph is full, which would be quite limiting.