In a given graph with $n$ vertices ,the degree of each vertex is less than or equal to $5$. Prove that the vertices can be coloured using only three colors such that the number of edges which have endpoints of same colour is atmost $n/2$
Attempts:
If the graph is a tree than it can be coloured using only 2 colours such that there is no SCE(edge with endpoints of same colour)
If there exists a cycle of 4 vertices , no. of sce is at most 1(after coloring)
If 5 vertices, then at most 2
If 6 vertices than at most 3.
I wasn't able to proof for more and also for combinations of cycles
Best Answer
Let $G$ be a graph with $n$ vertices and no vertex of degree greater than $5$. Then $3$-colour $G$ so as to minimise the number of SCE.
First suppose a vertex $v$ of colour $c$ is incident with two SCE. Then there is a colour $d$ such that $v$ is adjacent to at most one vertex of colour $d$. Changing $v$s colour to $d$ then reduces the number of SSE, a contradiction.
Each vertex is now joined to at most $1$ SCE. The total number of SCE is therefore less than or equal to $n/2$, as required.