Smallest Imperfect Graph who's chromatic number equals clique number So I need to find the smallest imperfect graph, $G$ who's chromatic number equals it's clique number. ie: $$\chi(G) = \omega(G)$$ Finding imperfect graphs isn't hard (since finding perfect graphs is). Even finding imperfect graphs with this property isn't too hard. But how do we find the _smallest_ graph (I assume minimal # vertices). Even if I have an idea what this graph is, how can I prove it is the smallest? I.e if I think sum graph on $n$ vertices is the smallest graph satisfying this, it seems daunting to show every graph of order $<n$ fails to satisfy this (unless $n$ is relatively small). Methods to approach and tackle this problem?

Consider the cyclic graph with five vertices $a,b,c,d,e$ and add a sixth vertex $f$ with edges $af$, $bf$, $df$. Then $\omega(G)=\chi(G)=3$ and the graph is not perfect becaus the induced subgraph obtained by removing $f$ has $\chi=3$ and $\omega=2$.

Why is six minimal? For graphs up to four vertices, $\chi=\omega$ always holds, hence every graph with at most five vertices having $\chi=\omega$ is perfect.