Graph theory find largest number of edges of graph

Question

Graph 10 vertices , 4 possible colorable vertex. Find the largest number of edges of the graph. here vertex coloring is consider for the graph

Is this also satisfy planar graph euler equation? 2=p-q+r

With p=vertex,q=edges,r=region

2=10-q+r

2=14-q

q=12

Am i right?

Answer 1

The problem statment does not mention that the graph is planar, hence you cannot use Euler. However, if in a 4-colouring we have $n_i$ vertices of colour $i$, $1\le i\le 4$, then there can only be edges between verties of different colour, i.e., at most $$\tag1 f(n_1,n_2,n_3,n_4):=n_1(n_2+n_3+n_4)+n_2(n_3+n_4)+n_3n_4.$$ If $n_4>n_3+1$, then note that $$f(n_1,n_2,n_3+1,n_4-1)=f(n_1,n_2,n_3,n_4)+n_4-n_3-1>f(n_1,n_2,n_3,n_4).$$ The same holds for any other case where $n_i>n_j+1$. We conclude that in such a graph with maximal number of edges, we have $|n_i-n_j|\le 1$ for all $i,j$. For a total of $10$ vertices, this means that two colours must occur at two vertices and the other two colours at three vertices. So by $(1)$, we can achieve up to $$f(2,2,3,3)=37 $$ edges.