The following labeled slide was presented in a first year discrete mathematics course. However, the adjacencies don't appear to be preserved (see the second illustration below).
If the vertices in the above graph on the left are arbitrarily labeled A to F, and we select the arbitrary vertex A for the vertex labeled A in the graph on the right, there appears to be no way to label the adjacent vertices such that it will not create an edge that connects two vertices (the other two A-adjacent vertices) that are not adjacent in the original graph.
Of the 3 nodes that that are connected to vertex A, whichever is chosen to be the endpoint at the bottom right of the supposedly isomorphic graph, will lead to a situation where the other two nodes adjacent to A, will also be adjacent to each other, despite this not being the case in the original graph.
If these are really isomorphic, how can the second graph given in the slide preserve all the adjacencies of the original graph? Obviously, the degrees of the vertices and the sum of degrees of the graphs are the same, and the second graph is a bijection of the first, but what about the adjacencies?
Best Answer
You are right that the two given graphs are not isomorphic, so there is a mistake. An easy way to tell them apart is that the graph on the left is bipartite: edges only go from $\{A,C,E\}$ to $\{B,D,F\}$. The graph on the right contains a $3$-cycle, so it is not bipartite.