How to read the mathematical notation for multigraphs: $$E \rightarrow V \cup[V]^2 $$

$E$ is a set of edges

$V$ is the set of vertices

I am having trouble especially with this part $$[V]^2 $$


(Reinhard Diestel, Graph Theory 5th Edition, Springer, p.28 )

A multigraph is a pair $(V,E)$ of disjoint sets (of vertices and edges) together with a map $E →V ∪ [V ]^2$ assigning to every edge either one or two vertices, its ends. Thus, multigraphs too can have loops and multiple edges: we may think of a multigraph as a directed graph whose edge directions have been ‘forgotten’. To express that $x$ and $y$ are the ends of an edge $e$ we still write $e = xy$, though this no longer determines e uniquely.

(Reinhard Diestel, Graph Theory 5th Edition, Springer, p.28 )

  • 1
    $\begingroup$ Can you give the source? $\endgroup$ Mar 20, 2020 at 19:22
  • $\begingroup$ As @CyclotomicField suggests, knowing the source of this notation would be helpful. That being said, the notation makes no sense to me. Typically, $|V|$ would denote the cardinality of $V$, hence $|V|^2$ is a positive integer. However, the set $V \cup |V|^2$ is then the union of two different kinds of objects (graph vertices and integers). This doesn't make sense to me. Are you sure you copied the notation correctly? $\endgroup$
    – Xander Henderson
    Mar 20, 2020 at 19:34
  • $\begingroup$ Sorry my bad, I guess I copied the notation wrong. The font in the book (or my eyes) were bad. I guess it should be a bracket. $\endgroup$
    – MScott
    Mar 20, 2020 at 20:20
  • $\begingroup$ Based on the quoted text, $[V]^2$ is the collection $\{ \{ v_1, v_2\} : v_1, v_2 \in V\}$. This is kind of like the Cartesian product $V\times V$, but we forget the order, thus $(v_1, v_2)$ and $(v_2, v_1)$ are indistinguishable. It seems unnecessary to me to include $V$ in this union. This is meant to account for loops, but it seems to me that a loop from $v$ to itself could just as easily be denoted by $\{v,v\}$. $\endgroup$
    – Xander Henderson
    Mar 21, 2020 at 6:04
  • $\begingroup$ @MScott: Did you find your answer in the comments? Or is there still a need for further explanation? $\endgroup$
    – Moritz
    Mar 25, 2020 at 21:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.