so I am studying about graphs from the book discrete maths by Keneth Rosen 7th edition.Pg:645 However, I am bit unsatisifed with one of the statements from the book. So I would like to get it reviewed from someone who knows. Text about influence graph from the book

Figure7 associated with the text

Here the textbook says that in figure 7 there is no multiple directed edges. However I can clearly see there is multiple directed edges between Brian and Yvonne. Is the textbook getting wrong here or I seriously need to look back my concepts? Please help me.


1 Answer 1


"Multiple edges", in this context, has a technical meaning. (Used informally, it's obviously nonsense, because of course the graph has more than one edge.) It means that edges cannot have multiplicity: the same edge cannot appear multiple times.

It is okay to have the edge $(\text{Brian}, \text{Yvonne})$ as well as the edge $(\text{Yvonne}, \text{Brian})$, because these are different directed edges. However, in this context, it would be meaningless to have two copies of the edge $(\text{Brian}, \text{Yvonne})$: what would it mean, to have Brian "influence Yvonne twice"?

I would not say that an influence graph is a widely-recognized term, so you don't have to worry about its definition in other contexts. However, the term simple directed graph is commonly used for graphs that don't have loops (edges of the form $(u,u)$) or multiple edges (multiple copies of the same edge $(u,v)$). Some sources will also just call this a directed graph and assume by default that it is simple, and say directed multigraph to allow loops and multiple edges.

It is also possible to make other sets of assumptions:

  • A loopless directed (multi)graph forbid loops, but allows multiple copies of the same edge.
  • An oriented graph (this is a less common term, but still often used) is even more restrictive, and forbids the thing that happens in the question: at most one of the edges $(u,v)$ or $(v,u)$ can exist. These directed graphs are called "oriented graphs" because they are exactly the class of graphs that can be obtained from undirected graphs by giving each edge an orientation.

You must log in to answer this question.

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