Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer
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$? – Shahab Feb 13 '12 at 16:46
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$]. – Henning Makholm Feb 13 '12 at 17:52
Thanks. Can you please take a look at the proof that I have attempted and tell me whether it is correct or not? – Shahab Feb 14 '12 at 14:44
@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)$. – Henning Makholm Feb 14 '12 at 16:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.