Doubt in a graph theory paper of Lovasz

I agree with your interpretation that $H'$ is the subgraph of $H$ induced by $V(H) \setminus \{a\}$ and $H^*$ is the subgraph of $H$ induced by $V(H) \setminus \{a,b\}$. In support of this, note that the three cases are stated as

• $H^*$ is discrete (has no edges),
• $H^*$ is not discrete and $\Delta(H') \le n-3$,
• $H^*$ is not discrete and $\Delta(H') = n-2$.

The third case is only possible if $H'$ has at least $n-1$ vertices, and in the third case, it is concluded that $d_H(b) = n-2$, which only follows if $H'$ includes the vertex $b$.

(The argument there is that in $H'$, no vertex other than $b$ can have degree $n-2$, because then it has degree $n-1$ in $H$, being also adjacent to $a$. But $\Delta(H) = n-2$. Therefore, if $\Delta(H') = n-2$, then it must be $b$ that has degree $n-2$ in $H'$, and since $ab \notin E(H)$, $b$ has degree $n-2$ in $H$ as well.)

---

Now on to your main question. In the first case, where $H^*$ has no edges, we know that $H = G^c$ has the following structure:

• Vertices $a$, $b$, and $v_1, \dots, v_{n-2}$.
• Edges $av_1, \dots, av_{n-2}$ and $bv_1, \dots, bv_k$ for some $0 \le k \le n-2$.

This is triangle-free, so by Proposition 2.3 in the paper, the dimension of $G$ is determined entirely by the edge chromatic number of $H$. If $\chi'(H) \le 1$, then $\dim G = \chi'(H) + 1$, and if $\chi'(H) \ge 2$, then $\dim G = \chi'(H)$.

To edge-color $H$, we must begin by coloring $av_1, \dots, av_{n-2}$ using $n-2$ distinct colors (since they all share the endpoint $a$). We can avoid using any more colors by coloring $bv_i$ the same color as $av_{i+1}$ (and, if we get all the way up to $bv_{n-2}$, coloring it the same color as $av_1$). Therefore $\chi'(H) = n-2$, and we conclude $\dim G = n-2$. (The lemma assumes $n \ge 5$, so in particular $\chi'(H) \ge 2$.)

I don't know if this is supposed to count as obvious, or if it's the intended argument, but at least it resolves the issue.