Chromatic polynomials II

In this week-late post I will talk some more about results and conjectures concerning chromatic polynomials of graphs and matroids. As the title suggests, this is a continuation from my April post on the same topic. At the end of that post I said that I would discuss complex chromatic roots of graphs, but here I’ve decided to talk about matroids instead.

The chromatic polynomial of graphs is defined in terms of number of colourings with a given number of colours; this definition does not extend to matroids for obvious reasons. However, the Recipe Theorem by Oxley and Welsh in [OW79] tells us that a function on graphs or matroids satisfying a deletion-contraction recursion is essentially an evaluation of the Tutte polynomial. Now the chromatic polynomial does satisfy this type of recursion, and in fact Tutte’s polynomial was first called by Tutte the dichromatic polynomial, since he saw it as a generalisation of the chromatic polynomial of a graph. If $T_G(x,y)$ denotes the Tutte polynomial of a graph $G$, then \[P(G,q)=(-1)^{|V(G)-k(G)}q^{k(G)}T_G(1-q,0).\]

This definition can easily be extended to matroids. However, the equivalent of the chromatic polynomial for matroids is called the characteristic polynomial, and it is very slightly different (in that is has a missing power of $q$ factor). The characteristic polynomial of a matroid $M$ is denoted as $C(M,q)$ and may be defined as \[C(M,q)=(-1)^{r(M)}T_M(1-q,0).\]

So if $G$ is a graph with $k(G)$ components and $M=M(G)$, then $C(M,q)=q^{-k(G)}P(G,q)$, which for our purposes means that the chromatic polynomial of a graph $G$ and the characteristic polynomial of its graphic matroid $M(G)$ are essentially the same. I’m not sure why this terminology was adopted, since the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix, hence has nothing to do with the characteristic polynomial of its graphic matroid. Anyway, let’s see what we can say about real chromatic roots of matroids. We can still talk about root-free intervals and upper root-free intervals in the same way as for graphs.

Just to recap, a real interval $(a,b)$ is a root-free interval for a family of matroids $\mathcal{M}$ if no matroid in  $\mathcal{M}$ has a chromatic root (i.e. a root of its characteristic polynomial) in the interval $(a,b)$, while $\mathcal{M}$ has an upper root-free interval if there is a real number $a$ such that no matroid in $\mathcal{M}$ has a real root larger than $a$. The class of all matroids does not have an upper root-free interval (since you can get arbitrarily large chromatic roots from graphs). Many of the results I mentioned for graphs in my previous post generalise to matroids. In particular, if $M$ is a loopless connected matroid, then:

  • $C(M,q)$ is an alternating polynomial with degree $r(M)$,
  • $C(M,q)$ is non-zero with sign $(-1)^{r(E)}$ for $q\in (-\infty,0)$,
  • $C(M,q)$ has a simple zero at $q=1$, and
  • $C(M,q)$ is non-zero with sign $(-1)^{r(E)+1}$ for $q\in (0,\frac{32}{27})$.

As for graphs, the first three results are easy to see if you write the chromatic polynomial in the right form. Namely

\[C(M,q)=\sum_{X\subseteq E(M)}(-1)^{|X|}q^{r(E)-r(X)}.\]

The fourth result above was proved for matroids by Edwards, Hierons and Jackson [EHJ98]. So the magic number $\frac{32}{27}$ is still magic for matroids.

If a class of matroids contains all graphic matroids, then it has no upper root-free interval (because of cliques). What about minor-closed classes of matroids not containing all graphs?

If you recall, Woodall and Thomassen proved independently that if $\mathcal{G}$ is a proper minor-closed family of graphs, then $(d(\mathcal{G}),\infty)$ is an upper root-free interval for $\mathcal{G}$, where $d(\mathcal{G})$ is the minimum number such that every graph in $\mathcal{G}$ has a vertex of degree at most $d$ (this is finite by a theorem of Mader). The surprising fact is that this result was published in 1997, while it is in fact implied by a more general and quite a bit older result for matroids. In 1978 Oxley proved the following.

Theorem 1: Let $D=\{x_1,\ldots,x_k\}$ be a cocircuit of a matroid $M$. Then \[C(M,q)=(q-k)C(M\backslash D,q)+\sum_{j=2}^{k}\sum_{i=1}^{j-1} C(M\backslash x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_{j-1}/x_i,x_j, q).\]

This looks a bit complicated, but by induction it implies the following.

Corollary 2: If all minors of a matroid $M$ have a cocircuit of size at most $k$, then $C(M,q)>0$ for all $q \geq k$.

Corollary 2 in turns implies that any proper minor-closed class of graphs has an upper root-free interval (i.e. the result of Woodall and Thomassen). It also implies the same result for matroids of bounded branch width. Unfortunately, minor-closed classes of matroids may not have bounded minimum cocircuit size, even if they don’t contain all graphic matroids, so the following is still wide open.

Conjecture 3: Every minor closed class of matroids that does not contain all graphic matroids has an upper root-free interval.

A very special but still very difficult case of this conjecture is the following.

Conjecture 4: The class of cographic matroids has an upper root-free interval.

Conjecture 4 has been studied quite a bit, since it is in fact a question on flows in graphs (the characteristic polynomial of a matroid is the flow polynomial of its dual). I’ll conclude the post with a bit of history on this problem.

Welsh conjecture that $(4,\infty)$ is an upper root-free interval for cographic matroids. For planar graphs this would imply the Birkoff-Lewis conjecture. However, Gordon Royle found counterexamples to this conjecture by looking at a family of graphs called generalised Petersen graphs. Based on the examples he found for which he could calculate the real roots, he modified Welsh’s conjecture, changing the 4 to a 5, as “$(5,\infty)$ is an upper root-free interval for cographic matroids”. However, this conjecture turned out to also be false, as proved by Jesus Salas and Jesper Jacobsen, who managed to show that some large generalised Petersen graph has real flow roots slightly over 5. Incidentally, in July I went to Royal Holloway to attend the Workshop on New Directions for the Tutte Polynomial and I saw Jesus Salas give a talk on this. You can have a look at his slides on the conference page. So now the question remains of whether cographic matroids do have an upper root-free interval, and if so, what the interval is.


[O78] J. G. Oxley, Colouring, packing and the critical problem, Quart. J. Math. Oxford Ser. (2), 29(113), pp 11-22, 1978.

[OW79] J. G. Oxley and D. J. A. Welsh, The Tutte polynomial and percolation, Graph Theory and Related Topics (eds. J. A. Bondy and U. S. R. Murty), pp. 329-339, Academic Press, London, 1979.

[EHJ98] H. Edwards, R. Hierons, and B. Jackson, The zero-free intervals for characteristic polynomials of matroids, Combin. Probab. Comput., 7(2), pp. 153-165, 1998.

[JS13] J. L. Jacobsen and Jesús Salas, Is the 5-flow conjecture almost false?, Journal of Comb. Theory Series B, 103(4), pp. 532-565, 2013.


The Matroid Secretary Problem

In this post, I am going to discuss the matroid secretary problem, which is a very nice problem introduced by Babaioff, Immorlica, and Kleinberg [1].  I will try to give an up-to-date account, but am far from an expert in this area, so please feel free to comment if I miss or muddle anything.

Let’s warm up with the classical secretary problem, which has the following setup.  We want to hire a secretary.  There is a set $X$ of $n$ candidates, and each $x \in X$ has a competency $w(x)$.  We know that there are $n$ candidates, but we do not know the competency function.  The secretaries are then presented to us in a random order.  Once a secretary is presented to us, we interview him and discover his competence.  We then have to make an irrevocable decision to hire him or not.  If we hire him on the spot, the process ends.  If not, then due to a hyper-competitive labour market, he will be hired by another firm, and we must move on to the next candidate.

Let OPT be the maximum competency of all secretaries.  Our goal is to devise an algorithm that hires a secretary with competency close to OPT.  Say that an algorithm $\mathcal A$ is $\alpha$-competitive if OPT / $\mathbb{E} (\mathcal A) \leq \alpha$, where $\mathbb{E} (\mathcal A)$ is the expected competency outputted by $\mathcal A$ for a random permutation $\sigma$ of $X$.

Here is a $4$-competitive algorithm for the classical secretary problem.  We reject each of first $\frac{n}{2}$ candidates but we keep track of the highest competency, say $h$, of the first $\frac{n}{2}$ candidates.  We then hire the first candidate with competency at least $h$ (if none exists, we just hire the last secretary).  This algorithm is $4$-competitive because the probability that the most competent secretary is in the second half and the second most competent secretary is in the first half is more than $\frac{1}{4}$.  Interestingly, if we instead reject $\frac{1}{e}$ of the initial candidates, we obtain an $e$-competitive algorithm, which turns out to be best possible over all possible algorithms [2].

The matroid secretary problem has the same setup as above, except that there is a matroid $\mathcal M$ on the underlying set $X$ of secretaries.  We now want to hire a set of secretaries, subject to the condition that our hired set is independent in $\mathcal M$.  Again, there is an unknown weight function $w:X \to \mathbb R_+$, and the secretaries are presented to us in a random order.  After interviewing $x$, we must make an irrevocable decision to add or not add $x$ to our currently constructed independent set $I$.  Again, the goal is to devise an algorithm whose expected output is close to the maximum weight independent set.

Note that we recover the classical secretary problem when $\mathcal M$ is a rank-$1$ uniform matroid.  The generalization to matroids might seem like abstract nonsense, but the matroidal version is actually relevant in the theory of auctions, and has garnered a lot of interest.  The big (and still open) problem is the following conjecture.

Conjecture 1 (Babaioff, Immorlica, and Kleinberg [1]).  For every matroid $\mathcal M$, there is a $O(1)$-competitive algorithm.

Using a clever modification of the threshold price algorithm that we discussed for the classical secretary problem, Babaioff, Immorlica, and Kleinberg [1] proved that there is a $O(\log r)$-competitive algorithm, where $r$ is the rank of $\mathcal M$.  In a breakthrough paper, Chakraborty and Lachish [3] devised a $O(\sqrt{ \log r})$-competitive algorithm.  Their algorithm is a patchwork of a few different algorithms, and is quite complicated.  Finally, the state-of-the-art is a $O( \log \log r)$-competitive algorithm of Lachish [4].  Using different tools, Feldman, Svensson, and Zenklusen [5] have also obtained a $O( \log \log r)$-competitive algorithm for general matroids.

Another line of research is to weaken the problem slightly, in the hope of obtaining a constant-competitive algorithm.  Perhaps the most important modification is known as the random assignment model.  Note that in the original matroid secretary problem, we may as well assume that the weight function is chosen by an adversary.  In the random assignment model, we weaken the adversary, by only allowing her to choose the set of weights.  The weights are then randomly assigned to the set of secretaries.  Soto [6] proved that there is a constant-competitive algorithm for all matroids in the random assignment model.

Theorem 2 (Soto [6]). For each matroid $\mathcal M$, there is a $O(1)$-competitive algorithm in the random assignment model.

Soto’s algorithm uses the classic decomposition of a matroid into its principal minors.  See the recent paper of Fujishige [7] for a survey of this theory.  The principal minors of a matroid are uniformly dense ($\mathcal M$ is uniformly dense if $\max_{A \subseteq E} \frac{|A|}{r(A)}$ is obtained by $E$). Using the decomposition, one can reduce to the case of uniformly dense matroids, and Soto proved that there is indeed a $O(1)$-competitive algorithm for uniformly dense matroids. Note that his proof crucially assumes that we are in the random assignment model.

There are also many other interesting variants of the original matroid secretary problem. See Section 3 of Dinitz [8] for a nice overview.

I will finish by discussing the original matroid secretary problem for restricted classes of matroids.  In [1], it is proved that Conjecture 1 holds for graphic matroids, uniform matroids, partition matroids, and bounded-degree transversal matroids.  The bounded-degree condition for transversal matroids was later removed by Dmitrov and Plaxton [9].

Here is another class of matroids for which Conjecture 1 holds.  Let $\mathcal F$ be a laminar family and $c: \mathcal F \to \mathbb{N}$.  If we let $\mathcal I$ be the set of all $I$ such that $|I \cap F| \leq c(F)$ for all $F \in \mathcal F$, then $\mathcal I$ is the set of independent sets of a matroid.  Matroids arising in this way are called laminar matroids.  Note that the class of laminar matroids contains the partition matroids.  Im and Wang [10] showed that there is a constant-competitive matroid secretary algorithm for the class of laminar matroids.

Finally, Dinitz and Kortsarz gave a $O(1)$-competitive algorithm for the matroid secretary problem on regular matroids.  Their proof uses Seymour’s decomposition theorem for regular matroids [11].  Note that graphic matroids, cographic matroids, and $R_{10}$ all have $O(1)$-competitive matroid secretary algorithms.

Using the structure theorem for $\mathbb F$-representable matroids proved by Geelen, Gerards and Whittle [12], it may be possible to prove the following special case of Conjecture 1.

Conjecture 3.  For every finite field $\mathbb F$, there is a $O(1)$-competitive algorithm for the matroid secretary problem on the class of $\mathbb F$-representable matroids.

I suspect this might be tricky since one basic class of $\mathbb F$-representable matroids are those representable over a subfield $\mathbb F’$ of $\mathbb F$, and I don’t see how to get a $O(1)$-competitive matroid secretary algorithm for  $\mathbb F’$-representable matroids unless we are doing some cunning induction.

On the other hand, the structure theorem for binary matroids is slightly simpler (due to the absence of subfields), so the following special case of Conjecture 3 may be doable.

Conjecture 4. There is a $O(1)$-competitive algorithm for the matroid secretary problem on binary matroids.


[1] Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proc. SODA, pages 434–443, 2007.

[2] E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Math. Dokl, 4, 1963.

[3] Sourav Chakraborty and Oded Lachish. Improved competitive ratio for the matroid secretary problem. In Proc. SODA, pages 1702–1712, 2012.

[4] Lachish, Oded. O(log log rank)-competitive ratio for the matroid secretary problem. Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on. IEEE, 2014.

[5] Feldman, Moran, Ola Svensson, and Rico Zenklusen.  A simple O(log log (rank))-competitive algorithm for the matroid secretary problem.  Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2015.

[6] José A. Soto. Matroid secretary problem in the random assignment model. In Proc. SODA, pages 1275–1284, 2011.

[7] S. Fujishige. Theory of principal partitions revisited. In Research Trends in Combinatorial Optimization, pages 127–162, 2009.

[8] Dinitz, Michael. Recent advances on the matroid secretary problem. ACM SIGACT News 44 (2013), no. 2, 126–142.

[9] Nedialko B. Dimitrov and C. Greg Plaxton. Competitive weighted matching in transversal matroids. In Proc. ICALP, pages 397–408, 2008.

[10] Sungjin Im and Yajun Wang. Secretary problems: laminar matroid and interval scheduling. In Proc. SODA, pages 1265–1274, 2011.

[11] P. D. Seymour. Decomposition of regular matroids. J. Combin. Theory Ser. B, 28(3):305–359, 1980.

[12] J. Geelen, B. Gerards, G. Whittle. Structure in minor-closed-classes of matroids. Surveys in Combinatorics, London Mathematical Society Lecture Note Series 409, 327–362, 2013.

Clutters I

I have been trying to firm up my feeling for the theory of clutters. To that end, I have been working through proofs of some elementary lemmas. For my future use, as much as anything else, I will post some of that material here.

A clutter is a pair $H=(S,\mathcal{A})$, where $S$ is a finite set, and $\mathcal{A}$ is a collection of subsets of $S$ satisfying the constraint that $A,A’\in\mathcal{A}$ implies $A\not\subset A’$. In other words, a clutter is a hypergraph satisfying the constraint that no edge is properly contained in another. For this reason we will say that the members of $\mathcal{A}$ are edges of $H$. Clutters are also known as Sperner families, because of Sperner’s result establishing that if $|S|=n$, then
\[\mathcal{A}\leq \binom{n}{\lfloor n/2\rfloor}.\]

Clutters abound in ‘nature’: the circuits, bases, or hyperplanes in a matroid; the edge-sets of Hamilton cycles, spanning trees, or $s$-$t$ paths in a graph. Even a simple (loopless with no parallel edges) graph may be considered as a clutter: just consider each edge of the graph to be a set of two vertices, and in this way an edge of the clutter. There is one example that is particularly important for this audience: let $M$ be a matroid on the ground set $E$ with $\mathcal{C}(M)$ as its family of circuits, and let $e$ be an element of $E$. We define $\operatorname{Port}(M,e)$ to be the clutter
\[(E-e,\{C-e\colon e\in C\in \mathcal{C}(M)\})\]
and such a clutter is said to be a matroid port.

If $H=(S,\mathcal{A})$ is a clutter, then we define the blocker of $H$ (denoted by $b(H)$) as follows: $b(H)$ is a clutter on the set $S$, and the edges of $b(M)$ are the minimal members of the collection $\{X\subseteq S\colon |X\cap A|\geq 1,\ \forall A\in\mathcal{A}\}$. Thus a subset of $S$ is an edge of $b(H)$ if and only if it is a minimal subset that has non-empty intersection with every edge of $H$. Note that if $\mathcal{A}=\{\}$, then vacuously, $|X\cap A|\geq 1$ for all $A\in \mathcal{A}$, no matter what $X$ is. The minimal $X\subseteq S$ is the empty set, so $b((S,\{\}))$ should be $(S,\{\emptyset\})$. Similarly, if $\mathcal{A}=\{\emptyset\}$, then the collection $\{X\subseteq S\colon |X\cap A|\geq 1,\ \forall A\in\mathcal{A}\}$ is empty, so $b((S,\{\emptyset\}))$ should be $(S,\{\})$. The clutter with no edges and the clutter with only the empty edge are known as trivial clutters.

Our first lemma was noted by Edmonds and Fulkerson in 1970.

Lemma. Let $H=(S,\mathcal{A})$ be a clutter. Then $b(b(H))=H$.

Proof. If $H$ is trivial, the result follows by the discussion above. Therefore we will assume that $H$ has at least one edge and that the empty set is not an edge. This implies that $b(H)$ and $b(b(H))$ are also non-trivial. Let $A$ be an edge of $H$. Now every edge of $b(H)$ has non-empty intersection with $A$, by the definition of $b(H)$. Since $A$ is a set intersecting every edge of $b(H)$, it contains a minimal such set. Thus $A$ contains an edge of $b(b(H))$.

Now let $A’$ be an edge of $b(b(H))$. Assume that $A’$ contains no edge of $H$: in other words, assume that every edge of $H$ has non-empty intersection with $S-A’$. Then $S-A’$ contains a minimal subset that has non-empty intersection with every edge of $H$; that is, $S-A’$ contains an edge of $b(H)$. This edge contains no element in common with $A’$. As $A’$ is an edge of $b(b(H))$, this contradicts the definition of a blocker. Hence $A’$ contains an edge of $H$.

Let $A$ be an edge of $H$. By the previous paragraphs, $A$ contains $A’$, an edge of $b(b(H))$, and $A’$ contains $A^{\prime\prime}$, an edge of $H$. Now $A^{\prime\prime}\subseteq A’\subseteq A$ implies $A^{\prime\prime}=A$, and hence $A=A’$. Thus $A$ is also an edge of $b(b(H))$. Similarly, if $A’$ is an edge of $b(b(H))$, then $A^{\prime\prime}\subseteq A\subseteq A’$, where $A’$ and $A^{\prime\prime}$ are edges of $b(b(H))$, and $A$ is an edge of $H$. This implies $A’=A^{\prime\prime}=A$, so $A’$ is an edge of $H$. As $H$ and $b(b(H))$ have identical edges, they are the same clutter. $\square$

If $H=(S,\mathcal{A})$ is a simple graph (so that each edge has cardinality two), then the edges of $b(H)$ are the minimal vertex covers. In the case of matroid ports, the blocker operation behaves exactly as we would expect an involution to do$\ldots$

Lemma. Let $M$ be a matroid and let $e$ be an element of $E(M)$. Then \[b(\operatorname{Port}(M,e))=\operatorname{Port}(M^{*},e).\]

Proof. Note that if $e$ is a coloop of $M$, then $\operatorname{Port}(M,e)$ has no edges, and if $e$ is a loop, then $\operatorname{Port}(M,e)$ contains only the empty edge. In these cases, the result follows from earlier discussion. Now we can assume that $e$ is neither a loop nor a coloop of $M$. Let $A$ be an edge in $\operatorname{Port}(M^{*},e)$, so that $A\cup e$ is a cocircuit of $M$. Since a circuit and a cocircuit cannot meet in the set $\{e\}$, it follows that $A$ has non-empty intersection with every circuit of $M$ that contains $e$, and hence with every edge of $\operatorname{Port}(M,e)$. Now $A$ contains a minimal set with this property, so $A$ contains an edge of $b(\operatorname{Port}(M,e))$.

Conversely, let $A’$ be an edge of $b(\operatorname{Port}(M,e))$. Assume that $e$ is not in the coclosure of $A’$. By a standard matroid exercise this means that $e$ is in the closure of $E(M)-(A’\cup e)$. Let $C$ be a circuit contained in $E(M)-A’$ that contains $e$. Then $C-e$ is an edge of $\operatorname{Port}(M,e)$ that is disjoint from $A’$. This contradicts the fact that $A’$ is an edge of the blocker. Therefore $e$ is in the coclosure of $A’$, so there is a cocircuit $C^{*}$ contained in $A’\cup e$ that contains $e$. Therefore $A’$ contains the edge, $C^{*}-e$, of $\operatorname{Port}(M^{*},e)$.

In exactly the same way as the previous proof, we can demonstrate that $b(\operatorname{Port}(M,e))$ and $\operatorname{Port}(M^{*},e)$ have identical edges. $\square$

This last fact should be attractive to matroid theorists: clutters have a notion of duality that coincides with matroid duality. There is also a notion of minors. Let $H=(S,\mathcal{A})$ be a clutter and let $s$ be an element of $S$. Define $H\backslash s$, known as $H$ delete $s$, to be
\[(S-s,\{A\colon A\in \mathcal{A},\ s\notin A\}\]
and define $H/s$, called $H$ contract $s$, to be
\[(S-s,\{A-s\colon A\in \mathcal{A},\ A’\in \mathcal{A}\Rightarrow A’-s\not\subset A-s\}.\]
It is very clear that $H\backslash s$ and $H/s$ are indeed clutters. Any clutter produced from $H$ by a (possibly empty) sequence of deletions and contractions is a minor of $H$.

We will finish with one more elementary lemma.

Lemma. Let $H=(S,\mathcal{A})$ be a clutter, and let $s$ be an element in $S$. Then

  1. $b(H\backslash s) = b(H)/s$, and
  2. $b(H/s) = b(H)\backslash s$.

Proof. We note that it suffices to prove the first statement: imagine that the first statement holds. Then
\[b(b(H)\backslash s)=b(b(H))/s=H/s\]
which implies that
b(H)\backslash s=b(b(b(H)\backslash s))=b(H/s)
and that therefore the second statement holds.

If $H$ has no edge, then neither does $H\backslash s$, so $b(H\backslash s)$ has only the empty edge. Also, $b(H)$ and $b(H)/s$ have only the empty edge, so the result holds. Now assume $H$ has only the empty edge. Then $H\backslash s$ has only the empty edge, so $b(H\backslash s)$ has no edges. Also, $b(H)$ and $b(H)/s$ have no edges. Hence we can assume that $H$ is nontrivial, and therefore so is $b(H)$.

If $s$ is in every edge of $H$, then $H\backslash s$ has no edges, so $b(H\backslash s)$ has only the empty edge. Also, $\{s\}$ is an edge of $b(H)$, so $b(H)/s$ has only the empty edge. Therefore we can now assume that some edge of $H$ does not contain $s$, and that therefore $H\backslash s$ is non-trivial and $\{s\}$ is not an edge of $b(H)$.

As $b(H)$ has at least one edge we can let $A$ be an arbitrary edge of $b(H)/s$, and as $\{s\}$ is not an edge of $b(H)$, it follows that $A$ is non-empty. Since $s$ is not in every edge of $H$, we can let $A’$ be an arbitrary edge of $H\backslash s$. Hence $A’$ is an edge of $H$. As $H$ is non-trivial, $A’$ is non-empty. If $A$ is an edge of $b(H)$, then certainly $A$ and $A’$ have non-empty intersection. Otherwise, $A\cup s$ is an edge of $b(H)$, so $A\cup s$ and $A’$ have non-empty intersection. As $A’$ does not contain $s$, it follows that $A$ and $A’$ have non-empty intersection in any case. This shows that every edge of $b(H)/s$ intersects every edge of $H\backslash s$, and thus every edge of $b(H)/s$ contains an edge of $b(H\backslash s)$.

As $H\backslash s$ is non-trivial, so is $b(H\backslash s)$. We let $A’$ be an arbitrary edge of $b(H\backslash s)$ and note that $A’$ is non-empty. Let $A$ be an arbitrary edge of $H$, so that $A$ is non-empty. If $s\notin A$, then $A$ is an edge of $H\backslash s$, so $A’\cap A\ne\emptyset$. If $s$ is in $A$, then $(A’\cup s)\cap A\ne\emptyset$. This means that $A’\cup s$ intersects every edge of $H$, so it contains an edge of $b(H)$ and therefore $A’=(A’\cup s)-s$ contains an edge of $b(H)/s$. We have shown that every edge of $b(H\backslash s)$ contains an edge of $b(H)/s$ and now the rest is easy. $\square$