The star graph of order n has the set of all permutations of {1,2,…,n} as vertex set and has an edge between any two vertices such that the corresponding permutations can be obtained from one another by swapping the first element with any other element (e.g. (1 2 3 4) will be connected to (3 2 1 4)). This drawing shows the star graph of order 4. Note. You can find many examples of beautiful graphs