recategorized by
187 views
0 votes
0 votes
A $\textit{proper edge coloring}$ of a graph is an assignment of colors to the edges so that any two edges sharing a common vertex should get different colors. Let $G$ be a graph with $20$ vertices that has a proper edge coloring with $6$ colors. The maximum number of edges in $G$ can be ______.
recategorized by

1 Answer

3 votes
3 votes
Proper edge coloring with 6 colors means a vertex can be connected with at max 6 edges. So maximum deg of any vertex in the graph G is 6. Total number of vertices is 20. So , 6 * 20 >= 2*|E| (E =number of edges)

So, 60 >= |E| .The maximum number of edges in Gcan be 60.

Related questions

0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4
admin asked Nov 30, 2021
112 views
Kamala tosses $11$ fair coins and Rajani tosses $10$ fair coins. The probability that the number of heads obtained by Kamala is more than the number of tails obtained by ...