Welcome to our community

Be a part of something great, join today!

Isomorphic representation

Joystar1977

Active member
Jul 24, 2013
119
Consider the complete graph with 5 vertices, denoted by K5.

C. Find an isomorphic representation (graph) of K5. Give the isomorphism mappings.

Can someone please tell me if this is correct?

One dot on graph = K1
One dot on graph = K2
One dot on graph = K3
One dot on graph = K4
One dot on graph = K5

K1 = points its connected to on graph
K2 = points its connected to on graph
K3 = points its connected to on graph
K4 = points its connected to on graph
K5 = points its connected to on graph

Would I have to make up an adjacency list and an adjacency matrix? Just asking this because when I watched a video on Youtube it mentioned this in a video about Isomorphic representation (graph). If this is not correct, then can somebody please correct it for me?
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
Consider the complete graph with 5 vertices, denoted by K5.

C. Find an isomorphic representation (graph) of K5. Give the isomorphism mappings.

Can someone please tell me if this is correct?

One dot on graph = K1
One dot on graph = K2
One dot on graph = K3
One dot on graph = K4
One dot on graph = K5
Phrases like "One dot on graph = K3" don't make sense to me. You have to have objects of the same type on both sides of the equal sign. You cannot say, "1 apple = 1 orange" because apples and oranges are not comparable. Similarly, "One dot on graph" is one dot, while K3 is a graph, not a dot. I am not sure how you compare the two.

K1 = points its connected to on graph
K2 = points its connected to on graph
K3 = points its connected to on graph
K4 = points its connected to on graph
K5 = points its connected to on graph
I don't understand "K3 = points its connected to on graph" either. Should it say, "it's"? What graph are you talking about?

The problem asks you to "give the isomorphism mappings". An isomorphism of K5 to itself is a mapping (more precisely, a bijection) from the set of vertices of K5 to the set of vertices of K5. If you denote vertices of K5 by 1, 2, 3, 4, 5, then an isomorphism is a bijection from the set {1, 2, 3, 4, 5} to itself. Note that every such bijection is a graph isomorphism because every two vertices of K5 are connected.
 

Joystar1977

Active member
Jul 24, 2013
119
Hello Evgeny.Makarov! I will let you know and try to explain deeper about what I mean.
Would the graph be drawn up kind of in the shape of a tree? Would I have to make up an adjacency list and adjacency matrix to see what points that K1, K2, K3, K4, and K5 are connected to? For example, if K1 is connected to points K2 and K3 then I would put a 1 and if they aren't connected to K4 and K5 then I would put a 0.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
Would the graph be drawn up kind of in the shape of a tree?
No. All graphs isomorphic to K5 are also K5; they all look the same.

Would I have to make up an adjacency list and adjacency matrix to see what points that K1, K2, K3, K4, and K5 are connected to? For example, if K1 is connected to points K2 and K3 then I would put a 1 and if they aren't connected to K4 and K5 then I would put a 0.
First, I think we are using K2, K3 and so on in different senses. It seems to me that when you write K2, you mean the second vertex of the graph K5. In fact, K2 is itself a graph, a complete graph on two vertices, i.e., two vertices connected by an edge.

Second, the problem statement does not ask you to make up an adjacency list and adjacency matrix. It asks you only to give the isomorphism mappings. I am not sure why "mappings" is in plural. According to Wikipedia,

"In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H
\[f \colon V(G) \to V(H)\]
such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H."

So, an isomorphism is a single map from vertices to vertices. To write such a map, you denote vertices (e.g., by 1, 2, 3, 4, 5) and then say which vertex is mapped into which vertex. For example, 1 is mapped to 4. Note that every bijection between vertices is a graph isomorphism in the case of somplete graphs.