Dark Mode

2,237 views

5 votes

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

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

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

- 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.)

5 votes

Best answer

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 )

3 votes

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.$