MHB How to Find an Isomorphic Representation for K5?

  • Thread starter Thread starter Joystar77
  • Start date Start date
  • Tags Tags
    Representation
AI Thread Summary
The discussion focuses on finding an isomorphic representation of the complete graph K5, which consists of five vertices. Participants clarify that the problem requires a bijection mapping from the vertices of K5 to itself, rather than creating adjacency lists or matrices. It is emphasized that K1, K2, etc., should not be confused with the complete graphs of fewer vertices, as they represent individual vertices in this context. The concept of isomorphism is explained, highlighting that any bijection between the vertices of K5 is a valid isomorphism due to the complete connectivity of the graph. The conversation concludes with a reminder that all graphs isomorphic to K5 retain the same structure as K5 itself.
Joystar77
Messages
122
Reaction score
0
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?
 
Physics news on Phys.org
Joystar1977 said:
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.

Joystar1977 said:
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.
 
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.
 
Joystar1977 said:
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.

Joystar1977 said:
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.
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top