1
$\begingroup$

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$.

1 Answers 1

2

$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).

  • 0
    @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)$.2012-02-14