# Questions tagged [multigraphs]

A multigraph is a graph that can have multiple edges with the same end nodes. Thus, two vertices may be connected by more than one edge.

21 questions
Filter by
Sorted by
Tagged with
10 views

### Why do the vertices in the resulting multigraph have even degree?

Suppose G(V,E) is a multigraph(i.e. we can have parallel edges in the graph) which contains a cycle C and for all vertices $v \in V$ we have that $deg(v)$ is even. Now suppose that we remove C from G ...
30 views

### Can a simple graph have weighted edges?

Can a simple graph have weighted edges or is it a multigraph as soon as it has weights? To me it seems like the adjacency matrix would look the same (as from a multigraph). Also I thought I had read ...
31 views

### How to read the mathematical notation for multigraphs?

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$$ ...
25 views

### All possible manipulations of multigraphs?

does anyone knows a paper/book, listing all possible simple manipulations of multigraphs? Like adding an edge here or removing a node there. I'd like to run an induction proof on all those cases, so i ...
45 views

### Disjoint cycles in a regular multigraph of even degree

Does a regular multigraph of even degree possess a set of cycles containing each vertex precisely once? [In a regular multigraph every vertex has the same degree. No loops are allowed but more than ...
28 views

### What is the name of a set of parallel edges in a multigraph?

In directed multigraph, two vertices, $a$ and $b$, may have zero or more parallel edges connecting them in one direction or the other. Does this set of parallel edges have a name? I seem to remember ...
52 views

339 views

### Topological sort of a subgraph of a multigraph

Is there a good algorithm for doing a topological sort of a subgraph of a multigraph? More specifically, given a multigraph G and a node n in the graph. Consider the subgraph G' all the nodes ...
Does there exist a multigraph $G$ of order $8$ such that the minimal $d(G) = 0$ while maximal $d(G) = 7$? What if ‘multigraph $G$’ is replaced by ‘graph $G$’? Answer: such multigraph does not exist, ...