2
$\begingroup$

I don't know if I am asking a silly question, but what is the exact definition of a graph homomorphism (throughout, the graphs may be assumed to be simple, i.e. undirected, no loops, no multiple edges, etc)? I have a slight confusion with the existing definition, which says that a function f : V(G) to V(H) is called a graph homomorphism, if whenever (i,j) is an edge of G, (f(i),f(j)) is an edge of H. The confusion is that, suppose that f(i) = f(j), and suppose that (i,j) is an edge of G. Then, is f still a homomorphism? Or does a graph homomorphism necessarily have to be an injective function (in set-theoretic sense)? Please help me settle this issue, as it would be very embarassing to have his kind of a misconception at the beginning of my study of graph theory!

$\endgroup$
1
$\begingroup$

Graph homomorphisms need not be injective on vertices. For example, arbitrary functions from a graph with no edges to another graph are always homomorphisms. What you've noticed is that two vertices sharing an edge cannot be identified if there are no loops, because an edge must be present in the image by definition.

$\endgroup$
  • $\begingroup$ Thanks, Matt. That resolves it! $\endgroup$ – user362064 Aug 18 '16 at 0:00
  • $\begingroup$ @user362064 No problem. $\endgroup$ – Matt Samuel Aug 18 '16 at 0:00

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.