What is a simple graph?
A simple graph, as opposed to a multigraph, is an undirected graph in which both multiple edges and loops are disallowed. In a simple graph the edges form a set (rather than a multiset) and each edge is an unordered pair of distinct vertices. In a simple graph with n vertices, the degree of every vertex is at most n − 1.
Share this highlighthttp://www.safaribooksonline.com/a/think-complexity/6594328/