0 votes
What is the maximum number of edges that can be present in a graph, that has 10 vertices, and has a valid vertex coloring with only 3 colors?
in Graph Theory by AlgoMeister (1.6k points)

2 Answers

+1 vote
 
Best answer

The following graph is a complete tripartite graph K3,3,4 and it is a case of a complete k-partite graph. When drawing this graph, I decomposed the vertices into three disjoint sets. Every vertex of each set graph vertices is adjacent to every vertex in the other two sets. Finally, it can be clearly seen from the graph that the maximum number of edges is 33.

--Updates--

To calculate the number of edges of K3,3,4 (Theoretically), I used the Hand-Shaking Theorem: 

The sum of degrees of all vertices = 2 | E |. 

The 3 vertices (dark blue) have degree 7,  3 vertices (red)  have degree 7, and last 4 vertices (light blue) have degree 6.
Therefore, the sum of the degrees of the vertices of K3,3,4 is (3x7) + (3x7)+ (4×6) = 66.
Thus, the total number of edges is 66 ÷ 2 = 33.

by AlgoMeister (920 points)
selected by
The explanation is clear!
+1 vote
i divide 10 points into 3 groups {3, 3, 4}, and link every point to the points in the other two groups.

so my answer is 4 * 6 + 9 = 33.
by (128 points)
reshown by
Could you give a drawing of this graph?

Related questions

The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...