retagged by
13,455 views
28 votes
28 votes
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 _______
retagged by

6 Answers

Best answer
14 votes
14 votes

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

edited by
32 votes
32 votes
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.$
8 votes
8 votes

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

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$

Answer:

Related questions

1 votes
1 votes
4 answers
2
admin asked Mar 30, 2020
2,990 views
Let $G$ be a simple undirected graph on $n=3x$ vertices $(x \geq 1)$ with chromatic number $3$, then maximum number of edges in $G$ is$n(n-1)/2$$n^{n-2}$$nx$$n$