A Multi-Edge Graph is a graph where there are multiple parallel edges between the same nodes. For example, multiples flights between two cities.