We shall define what a graph homomorphism is between two pseudographs, so that a graph homomorphism between two multigraphs, or two graphs are special cases.

Recall that a pseudograph $G$ is an ordered triple $(V,E,i)$ , where $V$ is a set called the vertex set of $G$ , $E$ is a set called the edge set of $G$ , and $i:E\to 2^V$ is a map (incidence map), such that for every $e\in E$ , $1\le |i(e)|\le 2$ .

Elements of $V$ are called vertices, elements of $E$ edges. The vertex/vertices associated with any edge $e$ via the map $i$ is/are called the endpoint(s) of $e$ . If an edge $e$ has only one endpoint, it is called a loop. $e_1$ and $e_2$ are said to be parallel if $i(e_1)=i(e_2)$ .

As two examples, a multigraph is a pseudograph such that $|i(e)|=2$ for each edge $e\in E$ (no loops allowed). A graph is a multigraph such that $i$ is one-to-one (no parallel edges allowed).

Definition. Given two pseudographs $G_1=(V_1,E_1,i_1)$ and $G_2=(V_2,E_2,i_2)$ , a graph homomorphism $h$ from $G_1$ to $G_2$ consists of two functions $f:V_1\to V_2$ and $g:E_1\to E_2$ , such that \begin{eqnarray} i_2\circ g=f^*\circ i_1. \end{eqnarray}The function $f^*:2^{V_1} \to 2^{V_2}$ is defined as $f^*(S)=\lbrace f(s)\mid s\in S\rbrace$ .

A graph isomorphism $h=(f,g)$ is a graph homomorphism such that both $f$ and $g$ are bijections. It is a graph automorphism if $G_1=G_2$ .

Remarks.

• In case when $G_1$ and $G_2$ are graphs, a graph homomorphism may be defined in terms of a single function $f:V_1\to V_2$ satisfying the condition (*)
  $\lbrace v_1,v_2\rbrace$ is an edge of $G_1\Longrightarrow \lbrace f(v_1),f(v_2)\rbrace$ is an edge of $G_2$ .
  To see this, suppose $h=(f,g)$ is a graph homomorphism from $G_1$ to $G_2$ . Then $f^*i_1(e)=f^*(\lbrace v_1,v_2\rbrace)=\lbrace f(v_1),f(v_2)\rbrace=i_2(g(e))$ . The last equation says that $f(v_1)$ and $f(v_2)$ are endpoints of $g(e)$ . Conversely, suppose $f:V_1\to V_2$ is a function sastisfying condition (*). For each $e\in E_1$ with end points $\lbrace v_1,v_2\rbrace$ , let $e^{\prime}\in E_2$ be the edge whose endpoints are $\lbrace f(v_1),f(v_2)\rbrace$ . There is only one such edge because $G_2$ is a graph, having no parallel edges. Define $g:E_1\to E_2$ by $g(e)=e^{\prime}$ . Then $g$ is a well-defined function which also satisfies Equation (1). So $h:=(f,g)$ is a graph homomorphism $G_1\to G_2$ .
• The definition of a graph homomorphism between pseudographs can be analogously applied to one between directed pseudographs. Since the incidence map $i$ now maps each edge to an ordered pair of vertices, a graph homomorphism thus defined will respect the ``direction'' of each edge. For example,
  
  are two non-isomorphic digraphs whose underlying graphs are isomorphic. Note that one digraph is strongly connected, while the other is only weakly connected.