# Graph coloring problem: existence of at least three vertices

I am trying to prove the following:

Fix an integer $d ≥ 3$. Let $H$ be a simple graph with all degrees $≤ d$ which cannot be $d$-colored and which is minimal (with the fewest vertices) subject to these properties. (i) Show that $H$ is nonseparable (this means that every graph obtained from $H$ by deleting a vertex is connected). (ii) Then show that if the vertex set $V(H)$ is partitioned into sets $X$ and $Y$ with $|Y| ≥ 3$, then there are at least three vertices $a, b, c ∈ Y$ each of which is adjacent to at least one vertex in $X$.

Using Brook's theorem is not allowed.

I have succeeded in proving part (i) and also in establishing that there can't be exactly $0$ or $1$ vertices in $Y$ adjacent to vertices in $X$. I need some help in proving the remaining thing, i.e. there can't be exactly $2$ vertices in $Y$ adjacent to vertices in $X$.

My textbook carries the following hint:

For part (ii), if the conclusion fails, then $H$ can be written as the union of two edge-disjoint subgraphs $A,B$ which intersect in two vertices $s, t$. Apply the induction hypothesis to graphs $A',B\,'$ obtained by adding an edge joining $s, t$ to $A,B$ respectively.

It's unclear to me what $A,B$ referred above are.

Thanks

Update: Here is my attempt at the proof according to the hint explained: Suppose, by way of contradiction, that there are exactly $2$ vertices $a,b$ in $Y$ adjacent to vertices in $X$.

Let $A$ be the subgraph of $H$ formed by the vertex set $V(Y)$ and all edges between the vertices of Y, and $B$ be the subgraph formed by the vertex set $V(X)\cup \{a,b\}$ and all edges with at least one end in $X$. Add the edge $ab$ to $A$ (only if its not there already in $A$) and the edge $ab$ to $B$. Call these new graphs $A'$ and $B'$ respectively, and note that since they both contain fewer vertices then $H$ so they may be d-colored. Further note that we may permute the colors of $B'$ so that the vertices $a,b$ are colored in the same colors in which they are colored in $A'$ and thus get a d-coloring of $A'\cup B'$.

Now $H$ is a subgraph of $A'\cup B'$ and this is a contradiction to the definition of $H$.

$A$ would be $Y$ plus all edges between nodes in $Y$, and $B$ would be have nodes $X\cup\{s,t\}$ and contain all edges that have at least one end in $X$. (Or vice versa).
• You didn't clarify what is $s,t$? Also if $t$ is in $B$ then what does the hint mean when it says add an edge from $t$ to $B$?
• We're assuming (in order to reach a contradiction) that $Y$ contains exactly two nodes that are connected to $X$. Call those two nodes $s$ and $t$. The hint should parse as [add an edge joining $s$ and $t$ to $A$] and [add and edge joining $s$ and $t$ to $B$]. Commented Feb 13, 2012 at 17:52
• @Shahab: Looks alright to me, except there seems to be no need to write $V(X)$ or $V(Y)$ when the problem defines $X$ and $Y$ as subsets of $V(H)$. Commented Feb 14, 2012 at 16:13