0
$\begingroup$

I'm a complete beginner in Graph Theory so apologies for the vague and basic nature of the question!

Wikipedia gives two options for the definition of a multigraph.

The first option (used, for example, by Wilson in Introduction to Graph Theory, 5th ed.) is:

A multigraph G is an ordered pair G := (V, E) with

V a set of vertices or nodes,

E a multiset of unordered pairs of vertices, called edges or lines.

The second option (used, for example, in Graph Theory by Bondy and Murty) is:

A multigraph G is an ordered triple G := (V, E, r) with

V a set of vertices or nodes,

E a set of edges or lines,

r : E → {{x,y} : x, y ∈ V}, assigning to each edge an unordered pair of endpoint nodes.

Question. The 2nd definition seems more cumbersome, why would you opt for this over the 1st?

$\endgroup$

1 Answer 1

1
$\begingroup$

The first definition does have the issue that a multiset may not be very rigurously defined, and it also has the issue that it may be harder to refer to a specific edge of the graph, and one may have to resort to something similar to the second definition when one wishes to use multiple edges in a proof.

$\endgroup$
2
  • $\begingroup$ Could you please point out the pages where the definitions you write about in your question are located. In my editions of both books (Robin J. Wilson, Introduction to Graph Theory, Fifth edition published 2010; J.A. Bondy, U.S.R. Murty, Graph Theory, Springer,2008), there is not even the term "multigraph". Although both books contain the term "multiple edges". $\endgroup$
    – kabenyuk
    Sep 16, 2021 at 12:31
  • $\begingroup$ Sorry, I should have said: both books call use the word "graph" for what wikipedia calls a "multigraph". $\endgroup$
    – user350031
    Sep 16, 2021 at 13:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .