# How can a parallel edge be identified?

An edge will have the same vertices as another edge that it is parallel to, so how can it be uniquely described?

• "An edge will have the same vertices as another edge that it is parallel to" - no it won't. May 31 '13 at 0:18

I would prefer to use a variant of the second definition offered by Zev. A multigraph has a set of vertices $V$, a set of edges $E$. The connection between vertices and edges can be described by a relation on $V\times E$, such that each edge is incident with one or two vertices (just one if you're not inclined to allow loops). Or it can be described by a function that assigns to each edge either one vertex or an unordered pair of vertices.
For an undirected multigraph, we simply have a multiset of edges, not a set. Thus, if $V=\{a,b,c\}$, we might have $$E=\{[(a,b),2],[(a,c),3]\},$$ which specifies that there are two edges connecting vertices $a$ and $b$, and three edges connecting vertices $a$ and $c$. We still can't technically distinguish "individual edges" between the same vertices; all we know is how many edges there are between any two vertices. However, for many purposes, that's all that's really necessary.
If you want to point to individual edges, you could take the approach typically used for directed multigraphs: we take a quadruple $(V,E,s,t)$, where $V$ is the set of vertices, $E$ is the set of edges, $s:E\to V$ is the function taking an edge to the vertex it starts at (its "source") and $t:E\to V$ is the function taking an edge to the vertex it ends at (its "target"). Then edges $e_1,e_2\in E$ are parallel with the same direction if $s(e_1)=s(e_2)$ and $t(e_1)=t(e_2)$, and parallel with opposite directions if $s(e_1)=t(e_2)$ and $t(e_1)=s(e_2)$.