GATE CSE 2020 | Question: 52

Question

Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______

Comments

If you know only basic then this answer is also good to understand how to solve this question :

1. Edge coloring for graph is assignment of colors to the graph edges such that no two incident edges have the same color.
2. here if asked for vertex coloring, the answer would be 3 (one color each for the two sets of vertices in given bipartite graph and 1 color for vertex 's')

3. This question is asking for edge coloring and not vertex coloring.

4. The vertex which is a part of highest number of incident edges is 's' as it has an edge to every other vertex of the graph. So there are 7 incident edges for this vertex and all of them need to be assigned a different/unique color.

5. So the minimum number of colors needed for edge coloring the given graph is 7

Answer 1

$\color{red}{\text{Detailed Video Solution, with Concept:}}$ https://youtu.be/42tvGJDgu-I 

Easiest & Correct way to solve it:

First understand the given graph $G$:

It has maximum degree $\Delta = 7,$ degree sequence $7,5,5,5,4,4,4,4$ (Vertex $s$ has degree $7$, three vertices have degree $5$ and remaining four vertices have degree $4$) 

---

Now, Some Important Theorems about Edge Coloring:

1. In the Edge Coloring of a graph $G:$ The least number of colors needed to color the edges of $G$ so that any two edges that share a vertex have different colors, is called Chromatic Index of $G$ and it is denoted by $\chi’(G).$

2. For any simple graph, $\chi’ \geq \Delta $ (Easy Proof HERE)  

For the given graph, $\Delta = 7,$ So, $\chi’ \geq 7.$

3. Vizing’s Theorem: For any simple graph, $\chi’ = \Delta$ OR $\Delta + 1.$

For the given graph, $\Delta = 7,$ So, $\chi’ = 7$ OR $8.$

Note that Graphs with $\chi’ = \Delta $ are called Class-1 graphs, and Graphs with $\chi’ = \Delta + 1$ are called Class-2 graphs.

4. MOST Interesting & Useful Result by Vizing:

Vizing proved that Every graph with a unique vertex of maximum degree must be Class-1. More specifically, he showed that every class two graph must have at least three vertices of maximum degree. 

So, if a graph $G$ has $\leq 2$ vertices of degree $\Delta,$ then $G$ is Class-1 graph, Hence, $\chi’(G) = \Delta.$

For the given graph, there is Unique vertex of maximum degree $\Delta = 7,$ So, given graph is Class-1, Hence, $\chi’(G) = 7.$

Detailed Video Solution, with Concept: https://youtu.be/42tvGJDgu-I 

Sources:

Source of Point 4: https://math.uchicago.edu/~may/REU2015/REUPapers/Green.pdf (Page 3, Paragraph 2)

https://core.ac.uk/download/pdf/82035825.pdf 

Comments

Probably, we can search things on internet and find many resources related to them but in exam,it is not easy to apply such properties if a new question comes because it requires a good memory to remember such properties which you have mentioned at the end.

As I had mentioned Determining whether a graph is class-1 and class-2, is generally hard. What if a new graph comes and the above property fails? Should we have to memorize properties according to the types of graphs ?

A question should be solved using some basic concepts or logic or some trick without memorizing many properties/formulae and accordingly question should be asked and that should be the purpose of an "aptitude" exam.

For some good graph theory books, all the chapters contain many theorems/properties/results in their exercises and it is difficult for a human being to memorize all these properties. (You can check the Douglas West's graph theory book and see the exercise questions).

Probably, these type of properties should be better suited for descriptive exams where someone needs to prove it.

---

@ankitgupta.1729 

As I had mentioned Determining whether a graph is class-1 and class-2, is generally hard.

I have mentioned the same HERE. 

The Proof of property 2 (mentioned in the answer) is also provided HERE.. 

Vizing’s theorem in property 3 is quite standard for chromatic index, so, at this point, students can find out that $\chi’(G) $ is either $7$ or $8.$

Now, if student is aware of the property $4$ then they can conclude that the answer is 7. Else, student needs to try to color the edges using 7 colors, & if they can, then conclude that the answer is 7, else 8. 

I am NOT in favor of “memorizing” tons of properties without understanding their proofs. If you watch GO Classes Graph Theory Course (or Complete Discrete Mathematics Course) then you will find out that more than 95% theorems/results/properties/formulae are taught with Proof. Rarely (Very Rarely) some property is given to the students without Proof (because the proof is extremely complicated Or long Or unnecessary etc).

Coming to this question Or a new question, as I already mentioned that a student can solve using the basic standard concepts.

 

---

Cool

Answer 2

This question is asking for edge coloring and not vertex coloring.

Had it been asked for vertex coloring, the answer would be $3$ (one color each for the two sets of vertices in given bipartite graph and $1$ color for vertex 's')

Edge coloring for graph is assignment of colors to the graph edges such that no two incident edges have the same color.

The vertex which is a part of highest number of incident edges is 's' as it has an edge to every other vertex of the graph. So there are $7$ incident edges for this vertex and all of them need to be assigned a different/unique color.

So the minimum number of colors needed for edge coloring the given graph is $7.$

Comments

-- Edge chromatic number or chromatic index of any simple undirected graph is either $d_{max}$  or $d_{max} + 1$ according to Vizing's Theorem.
https://en.wikipedia.org/wiki/Edge_coloring#Vizing's_theorem
So, here, minimum number of colors can be 7 or 8. So, we have to convince ourselves that minimum number of colors required to proper color the edges of the given graph can't be 8 by making atleast  one graph which required only $7$ colors for proper edge coloring.
https://gateoverflow.in/?qa=blob&qa_blobid=10132893589318938572

-- Suppose, maximum degree of a graph $G$ is $\Delta(G).$
if $|E| > \Delta(G)*\left \lfloor \frac{|V|}{2} \right \rfloor  $ then graph $G$ requires $\Delta(G) + 1 $ minimum colors for edge coloring of graph. But if $|E| \ngtr \Delta(G)*\left \lfloor \frac{|V|}{2} \right \rfloor  $ then graph $G$ requires $\Delta(G) $ . It is wrong statement. Counter-example is Petersen graph with 10 vertices, 15 edges and maximum degree=3. Petersen graph requires 4 colors with maximum degree=3 for proper edge-coloring.

-- All regular graphs $G$ with odd no. of vertices requires $\Delta(G) + 1$ minimum no. of colors for   proper edge-coloring. For example-Triangle.

---

Plz see both image . . . .

---

Nice explanation @ankitgupta.

We need to check if 8 colors requires or not.

 

https://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/coloring.htm

Answer 3

Maximum degree of a graph does not decide the minimum number of colors required to edge-color the simple graph $G.$

For Example, consider a $C_3$ (In the mentioned comment, I have called it as a triangle in the informal way at the end ) as:

This graph has maximum degree as $2$ but it can’t be colored with minimum number of $2$ colors so that adjacent edges have the different colors.

Vizing and Gupta independently proved that $\Delta(G)  + 1$ colors suffice when $G$ is simple where $\Delta(G)$ is the maximum degree of a simple graph $G.$

So, if $G$ is simple then $\chi’(G) \leq \Delta(G)  + 1$ ($\chi’(G)$ is the edge-chromatic number or chromatic index of the graph $G$)

(Proof is given on wikipedia and in various graph theory books.) 

Note:

1. A simple graph $G$ is $\textbf{Class-1}$ if  $\chi’(G) = \Delta(G)$ and $\textbf{Class-2}$ if  $\chi’(G) = \Delta(G) + 1$ and determining whether a graph $G$ is Class-1 or Class-2 is generally hard.
2. If $G$ is bipartite then $\chi’(G) = \Delta(G)$
3. The Petersen Graph is $4-$ edge-chromatic though maximum degree in this graph is $3.$ 

Answer 4

To proper colour a graph,

For vertex-colouring, we need at least the size of max clique present in the graph.

For edge-colouring, we need at least the max degree of the graph. // Here it is 7

For minimum, we might need one more colour at times. e.g $K_3$, $K-5$