0
$\begingroup$

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'$.?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.