Hello everyone interested. Here's a problem that seems easy to state but has been hard for me to prove.
Consider a simple graph $G=(V,E)$ (V the vertices, E the edges). Let g be the complementary graph on the complementary edges $\binom n{2}-E$.
If g has two edges, what can the chromatic number $\chi(G)$ be?
I think the answer is related to this question I have: Is it true that for all graphs $G$ with n vertices, we have $\chi(G)+\chi(g)\leq n+1$?
Both of these have given me a hard time because I tried to count the cases, which becomes hard even for small number of vertices.
Is there a theorem I can employ that I am not seeing? Is counting the only way to answer?
Thanks in advance...
As mentioned in the comments, counting cases is a natural way to start off here. $g$ has exactly two edges, so either the edges share a vertex or have nothing in common.
In the first case, call the common vertex $v$. Then the subgraph of $G$ consisting of all the vertices except $v$ has all its edges - in particular it is complete. So, $G - \{v\}$ requires $n-1$ colours. Adding $v$ back in, it is not adjacent to some $u \in G - \{v\}$, so assign $v$ the same colour as $u$. This yields a valid colouring of $G$ since $u$ shares an edge with everything else in $G-\{v\}$, so must have a different colour. (Clearly $G$ cannot be coloured with fewer than $n-1$ colours since it has a subgraph which requires $n-1$ colours.) So, $\chi(G) = n-1$.
In the second case, use a similar argument. Suppose the edges are $(u_1,v_1)$ and $(u_2,v_2)$. Then $G - \{u_1,u_2\}$ is complete on $n-2$ vertices, so requires $n-2$ colours. Then, add $u_1$ and $u_2$ back in, giving $u_1$ the same colour as $v_1$ and $u_2$ the same colour as $v_2$. As before, we get that $\chi(G) = n-2$.