Complete A complete graph is a graph with N vertices in which every pair of vertices is joined by exactly one edge. The symbol used to denote a complete graph is KN. Example 6.4.2: Complete Graphs Figure 6.4.2: Complete Graphs for N = 2, 3, 4, and 5 a. K2 b. K3 c. K4 d. K5 two vertices and one three vertices and three four vertices and six five vertices and ten edge edges edges edges In each complete graph shown above, there is exactly one edge connecting each pair of vertices. There are no loops or multiple edges in complete graphs. Complete graphs do have Hamilton circuits. Reference the starting point of a Hamilton circuit Example 6.4.3: Reference in a Complete Graph Many Hamilton circuits in a complete graph are the same circuit with different starting points. For example, in the graph K3, shown below in Figure 6.4.3, ABCA is the same circuit as BCAB, just with a different starting point (reference point). We will typically assume that the reference point is A. Figure 6.4.3: K3
Complete A complete graph is a graph with N vertices in which every pair of vertices is joined by exactly one edge. The symbol used to denote a complete graph is KN. Example 6.4.2: Complete Graphs Figure 6.4.2: Complete Graphs for N = 2, 3, 4, and 5 a. K2 b. K3 c. K4 d. K5 two vertices and one edge three vertices and three edges four vertices and six edges five vertices and ten edges In each complete graph shown above, there is exactly one edge connecting each pair of vertices. There are no loops or multiple edges in complete graphs. Complete graphs do have Hamilton circuits. Reference the starting point of a Hamilton circuit Example 6.4.3: Reference in a Complete Graph Many Hamilton circuits in a complete graph are the same circuit with different starting points. For example, in the graph K3, shown below in Figure 6.4.3, ABCA is the same circuit as BCAB, just with a different starting point (reference point). We will typically assume that the reference point is A. Figure 6.4.3: K3
Chapter_6_GraphTheory.docx