## The Possible Number of Paths For a Complete Graph

A complete graph is such that every vertex is connected to every other vertex directly exactly once. If a complete graph has n vertices, it is called The following graphs are all complete. A path is a route between any two vertices.

If a graph has two nodes A and B, there are two paths with one vertex, A and B, and two paths AB and BA with two vertices.

If a graph has three vertices A, B and C, there are three paths with one node, A, B and C. If the path has more than one node we can choose start and end vertices in 3*2=6 ways (AB, AC, BC, BA, CA and CB). Each of these can be a path direct from start vertex to end vertex or with an intermediate vertex, giving the other paths ACB, ABC, BAC, BCA, CBA and CAB hence 3+6+6=15 paths altogether.

In general for a graph with vertices we can choose paths with one vertex in different ways. and for a path with two or more vertices we can choose start and end points in ways.

We have then paths with two vertices.

We can have paths with intermediate vertices. Suppose we have one intermediate vertex. This is chosen from the remaining vertices so there are paths with three vertices.

Suppose we have two intermediate vertices. These are chosen from the remaining vertices, and since to choose the vertices in a different order determines a different path, we can choose the two intermediate vertices in different ways so there are different paths.

Continuing in this way until all the vertices are chosen, giving paths and adding we obtain possible paths for a complete graph with vertices.

For as before. 