A graph whose edges are unordered pairs of vertices, and the same pair of vertices can be connected by multiple edges. Formal Definition: Same as graph, but E is a bag of edges, not a set.