0
$\begingroup$

If $H=(V,E)$ is a hypergraph then we say that $C\subseteq V$ is a cutset if $C\cap e \neq \emptyset$ for all $e\in E$. We set $$\text{cut}(H) = \min\{|C|: C \text{ is a cutset of }H\}.$$ A subset $D\subseteq E$ is said to be a disjoint if the members of $M$ are mutually disjoint. Set $$\text{disj}(H) = \sup\{|D|: D\subseteq E\text{ is disjoint}\}.$$ An easy argument shows that $\text{disj}(H) \leq \text{cut}(H)$ for any hypergraph $H$.

Question. If $G = (V,E)$ is a simple, undirected graph with $\text{cut}(G) = \text{disj}(G)$, is there necessarily a disjoint set $D_0\subseteq E$ and a (minimal) cutset $C_0$ such that $|C_0\cap d| = 1$ for all $d \in D_0$?

$\endgroup$
4
  • $\begingroup$ take any maximal disjoint set and any minimal cutset, an easy argument which you mentioned shows that this works $\endgroup$ May 16, 2022 at 10:25
  • $\begingroup$ The minimal cutset might intersect the maximal disjoint set in more than $1$ point depending on how the other edges are situated... or am I wrong? $\endgroup$ May 16, 2022 at 12:07
  • 2
    $\begingroup$ it must intersect each edge in this disjoint family at least once, but it has as many elements as we have disjoint sets $\endgroup$ May 16, 2022 at 12:45
  • 3
    $\begingroup$ @FedorPetrov You are assuming that the graph is finite, which was not stated. On the other hand, if infinite graphs are allowed, then any infinite complete graph is a trivial counterexample. $\endgroup$
    – bof
    May 16, 2022 at 23:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.