3,167 views

The following simple undirected graph is referred to as the Peterson graph.

Which of the following statements is/are $\text{TRUE}?$

1. The chromatic number of the graph is $3.$
2. The graph has a Hamiltonian path.
3. The following graph is isomorphic to the Peterson graph.

1. The size of the largest independent set of the given graph is $3.$ (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)

Answer : Option A,B and C are TRUE

Given graph is Petersen graph. $3$ colors are sufficient and necessary to color it.

Hamiltonian path exists in Peterson graph but not Hamiltonian cycle.

It’s chromatic number is 3 but note that doesn’t mean largest independent vertex set size is 3.

It has largest independent vertex size = 4 (red colored vertices in first graph)

Graph present in Option C is isomorphic to Peterson graph ( Isomorphic : we need to see it in another perception )

Adding for options A and C..

From fig (1), it is cleared that Petersen Graph contains a $5-$ cycle $1-2-3-4-5-1$ and if a graph contains an odd cycle ( i.e. number of vertices are odd) then it can’t be properly colored with $2$ colors. So, here minimum $3$ colors are required so that no two adjacent vertices have the same color. It shows that we can’t color the graph with 2 colors, we need at least 3 colors for proper coloring and since, there exist a $3-colored$ graph (as mentioned in this answer), we can say that Chromatic Number of the Petersen Graph is $3$.

Now, in option (C), we need to prove that given $2$ graphs are isomorphic in nature.

Since, Two Graphs $G_1$ and $G_2$ are isomorphic i.e. $G_1 \cong G_2$ if there is a bijection $f: V(G_1) \rightarrow V(G_2)$ between the sets of vertices of graphs $G_1$ and $G_2$ such that $(u,v)$ is an edge in graph $G_1$ iff $(f(u),f(v))$ is an edge in graph $G_2$

In fig(1) and fig(2), I have shown the labelling of vertices and constructed a bijection between the set of vertices of both graphs.

With some arrangement of vertices from fig(2), we can get fig(1). In fig (1), There is a pentagon of vertices 6,7,8,9,10 and there is a star like structure inside the pentagon with vertices 1,2,3,4,5 and both are connected by $5$ edges. To get this figure (1), put vertices 1 to 10 in space as in fig (1) and include edges between these vertices according to fig(2), it will give the same structure as in fig(1) and it verifies “$(u,v)$ is an edge in graph $G_1$ iff $(f(u),f(v))$ is an edge in graph $G_2” part of the above definition of isomorphism. So, based on the above labelling of the mentioned graph of option (C), we can say that both graphs are isomorphic. option c Showing The transition of Peterson’s graph to the 9-length cycle graph It’s Petersen, not Peterson (based on a mathematician Julius Petersen) Even in question, “Peterson” is mentioned. Spelling mistake is not an issue at all for me but still curious to know whether this spelling mistake is here or it was there in the original question paper also ? @ankitgupta.1729 To avoid mistakes we always try to upload the original paper itself and then do edits. You can click on the “edited” link near the question title to see the changes – the typo is there in original paper as well. https://gateoverflow.in/revisions/371896 The Peterson spelling may also be an Americanized form of similar non-English surnames such as Petersen or Pettersson” edited Although it’s a great answer from @Shaik Masthan and also @ankitgupta.1729 I would like to share an easier and fast approach I had followed in the exam for this question. For Option A and D, I had used the concept of Chromatic Partition. This is a very easy method which was highlighted by @Ayush Upadhaya Sir here https://gateoverflow.in/204092/gate-cse-2018-question-18?show=219861#c219861. First let us name each vertex, then it will be easier. Basically, if we construct the Maximal Independent Sets, we get: {A,C,J,I}, {B,D,F}, {E,G,H} Now we have to select minimum number of such sets which can include all vertices of graph. Here it is {A,C,J,I}, {B,D,F}, {E,G,H} .We can see that their union gives all the 10 vertices. Therefore only 3 sets are enough and we just need 1 colour to colour each set. Hence total 3 colours arre needed. Hence Chromatic Number is 3. This proves option A as True. Also, we can see that the largest independent set is of size 4. Hence option D is False straightaway. Even Option B is easy as only Hamiltonian Path is asked. There can be many paths. One of them:- So Option B is also True. For Option C, we can follow any of the two answers here. Edit (by ankitgupta.1729): Changed {A,C,J,I}, {B,D,F,G}, {E,B,G,H} to {A,C,J,I}, {B,D,F}, {E,G,H} because as a typo, G and B were mentioned twice. Thank you for such amazing explanation. @Shaik Masthan The new images are fine right? Yes sir. Thanks for this beautiful explanation 😊 This answer mostly focuses on the option$(C)$i.e. proving one graph is pairwise isomorphic to another graph but I will go through the other options as well in different way. I feel for the given graph, transforming one graph to another graph might take much time in exam and still it might be possible that we will not be able to show that both graphs are isomorphic to each other. So, I will show an easier method here and mostly I will deal with numbers without making graph and prove the results. Answer is long due to explaining things.$\textbf{Definition:}$The Petersen Graph is the simple graph whose vertices are$2-$element subsets of a$5-$element set and whose edges are the pairs of disjoint$2-$element subsets. Here,$[5] = \{1,2,3,4,5\}$is our$5-$element set and$2-$element subsets of this$5-$element set are$\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\},\{4,5\}.$Now, we write the pair$\{a,b\}$as$ab$or$ba.$So, for the given Petersen graph, we have vertex set as$\{12,13,14,15,23,24,25,34,35,45\}$Now, according to definition, edges are the pairs of disjoint$2-$element subsets. So, for example,$12$and$45$are disjoint, it means they are adjacent vertices when we form the graph but$12$and$13$are not. Now, to show that the above graphs are pairwise isomorphic, it suffices to name each of the vertices based on the given definition. If we are able to do it then they are isomorphic otherwise not and it is much easier to name them which is shown as below: The above definition is called the “Disjointness definition of adjacency” and this definition is present in most of the graph theory books (at least all the books which I have read). Even a book is written only on the Petersen Graph (Halton-Sheehan[1993]) and there are total$5! = 120$isomorphism from Petersen graph to itself. Basically, Isomorphism is an “equivalence relation” on the set of simple graphs but adjacency relation is not an equivalence relation on the set of vertices. To prove statements given in all the$4$options for a given question are not easy for a general graph$G.$There is no linear time in both$|V|$and$|E|$i.e.$\Theta(|V| + |E|)$algorithm for each of the given options for a general graph. It might be easy to disprove that two graphs are not isomorphic pairwise but it might be difficult to prove that they are isomorphic. We can use various graph-invariants like number of vertices, number of edges or number of cycles etc to tell that they are not isomorphic but it is difficult to tell that they are pairwise isomorphic graphs. If you can’t remember the above definition then either you can use the bijection property which I have mentioned in the comment of another answer or the following rules can be used to show isomorphism but it might be time consuming for large graphs.$(1)$Two graphs$G$and$H$are pairwise isomorphic iff their complements are isomorphic.$(2)$Showing the adjacency matrices with vertices ordered so that the matrices are identical is another way to prove that two graphs are isomorphic. It means if we have two graphs$G$and$H$and the adjacency matrices are$A(G)$and$A(H).$If we can convert$A(G)$to$A(H)$by interchanging rows and columns (note that if interchange two rows then corresponding columns will also be interchanged) then we can say two graphs are isomorphic. Now, comes to independent sets. We can find independent sets without checking the graph. We have to play with numbers only. An independent set in a graph is a set of pairwise nonadjacent vertices. Now, to find the non-adjacent vertices based on the above definition, we have to find collection of subsets which have one element common. For example, for element$5$we can make collection of subsets which have only one element common as$\{\{1,5\},\{2,5\},\{3,5\},\{4,5\}\}$i.e.$\{15,25,35,45\}$and similarly for element$4,$we can make collection as$\{14,24,34\}$and for$3,$we can make collection as$\{13,23\}$and for$2,$we can make collection as$\{12\}.$This collection is nothing but the partition of vertices which are making making independent set. So here we are getting$4$independent sets as:$1)\{15,25,35,45\}2)\{14,24,34\}3)\{13,23\}4)\{12\}$Now, here you can see the largest independent set i.e.$\{15,25,35,45\}$has size$4.$Now, comes to chromatic number. Chromatic Number$\chi (G)$is the minimum number of independent sets needed to partition$V(G).$We got$4$independent sets but is it possible to merge some sets to other so that it will still be independent set. The answer is yes. We can merge sets$\{13,23\}$and$\{12\}$and get a new set$\{12,13,23\}.$Now, you can see that all$12,13$and$23$have at least one element common pairwise. Now, we can check we can’t merge set now. Hence, we get the following independent sets:$1)\{15,25,35,45\}2)\{14,24,34\}3)\{12,13,23\}$This is the minimum possible number of independent sets needed to partition$V(G)$because merging is not possible now. Hence, chromatic number for the given graph is$3.$Now, to show that Hamiltonian Path exists we have to make a list from the vertex set$\{12,13,14,15,23,24,25,34,35,45\}$such that take element from this vertex set one by one according to the definition it means if we have$ab$in the list then we should not have to add elements like$ac$or$bd$and also, if we are adding new element then we have to check whether this new element is already in the list or not. So, say our list is$L=[]$and starting to fill this list with$12$and then$35$and then$14$and if we keep doing this, we can get one of the possible lists as$L =[12,35,14,23,45,13,24,15,34,25].$Here, each element in the list is in sequence and shows the hamiltonian path. To visualize, there are two more ways to show hamiltonian path. In the above two figures, figure$1$has an star like structure in thee middle which is isomorphic to$C_5$i.e. a cycle with$5$vertices. So, we have two disjoint$C_5$cycles which are connected by$5$edges as: Now, vertex-sequence$1,2,3,4,5,6,7,8,9,10$makes the Hamiltonian path for this graph as well as for the given graph because both are pairwise isomorphic. The another way is to see the above figure$(2)$where Hamiltonian path can be found easily for vertex sequence as$34,15,24,13,25,14,23,45,12,35.\$