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 theremaining 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 withvertices.
For
as before.