We say that a hypergraph $H=(V,E)$ is connected if the following condition holds:

for all $S\subseteq V$ with $\emptyset\neq S \neq V$ there is $e\in E$ that meets both $S$ and $V\setminus S$, i.e. $$S\cap e \neq \emptyset \neq (V\setminus S)\cap e.$$

Given $H=(V,E)$ connected, is there $E_0\subseteq E$ with the following properties?

  1. $(V,E_0)$ is connected, and
  2. whenever $E'\subseteq E_0$ with $E'\neq E_0$ then $(V,E')$ is no longer connected.

1 Answer 1


Let $V=E=\omega$. Connected subgraphs are precisely those which contain as edges $n$ for arbitrarily large $n$. Clearly there is no minimal such subgraph.

  • $\begingroup$ Could you clarify on the edges? Is there only one edge, or every edge is an element of $ω$? $\endgroup$ Commented Sep 18, 2019 at 11:29
  • 3
    $\begingroup$ @Bullet51 $E=\omega=\{0,1,2,3,\dots\}=\{\{\},\{0\},\{0,1\},\dots\}$. That is, edges are the (proper) initial segments of $\omega$. Perhaps I went a little too far trying to make my answer as concise as possible :P $\endgroup$
    – Wojowu
    Commented Sep 18, 2019 at 11:32

Your Answer

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

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