Finding the Number of Paths for a Complete Graph

It's only fair to share...Share on FacebookTweet about this on TwitterPin on PinterestShare on Google+Share on RedditEmail this to someone

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 calledThe 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 withvertices 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 inways.

We have thenpaths with two vertices.

We can have paths with intermediate vertices. Suppose we have one intermediate vertex. This is chosen from theremaining vertices so there arepaths 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 indifferent ways so there aredifferent paths.

Continuing in this way until all the vertices are chosen, givingpaths and adding we obtainpossible paths for a complete graph withvertices.

Foras before.

Comments are closed.