Multigraph definition confusion

266 Views Asked by At

I've started Graphs, Algorithms, and Optimizaton by Kocay and Kreher. They describe a multigraph as having more than one edge between the same end point vertices. . .

. . . an edge can then no longer be defined as a pair of vertices (or the multiple edges would not be distinct), but to each edge there still correcsponds a pair $\{u,v\}$. We can express this formally by saying that a graph $G$ consists of a vertex set $V(G)$, and edge set $E(G)$, and a correspondence $\psi : E(G) \rightarrow (\frac{V(G)}{2})$. Given an edge $e \in E(G)$, $\psi(e)$ is a pair $\{u,v\}$ which are the endpoints of $e$. Different edges can then have the same endpoints.

I guess I don't understand what the $\rightarrow$ is doing. They don't mean adjacency, do they? The $(\frac{V(G)}{2} )$ is the set of all vertex pairs, right? Earlier it said $E(G) \subseteq (\frac{V(G)}{2}) $, that is, the edge set and the vertex set respectively, where the edge set is a subset or equal to all the vertex pairs. How does this $\psi$ definition allow us to define multiple unique edges per vertex pair?