Simple Graph

Simple Graph is a Graphs with no loops (edges from a vertex to itself) and no parallel edges (more than one edge between the same pair of vertices).

In a simple graph with n vertices, each Vertex can have a degree of at most n-1, since there are only n-1 other vertices it can connect to. Any more connections would need a loop or a parallel edge.

A Complete Graph is a simple graph where every pair of vertices is connected. See Week 13 - Graphs A.