Let $H=(V,E)$ be a hypergraph, where $V\neq \emptyset$ is a set, and $E\subseteq {\cal P}(V)$. We say that $H$ is connected if whenever $S\subseteq V$ with $\emptyset \neq S \neq V$, there is $e\in E$ with $$e\cap S \neq \emptyset \neq e\cap (V\setminus S).$$ It is easily verified that any graph (finite or infinite) is connected if and only if the condition above is met.

For any connected graph, we can reduce the edge set such that the resulting graph is minimally connected: the spanning tree. This prompts the question whether the same holds for hypergraphs:

Question. If $H=(V,E)$ is a connected hypergraph, is there $E_0\subseteq E$ with the following properties?

  1. $(V,E_0)$ is connected, and
  2. for $E_0'\subseteq E_0$ with $E_0'\neq E_0$ we have that $(V,E_0')$ is not connected.

No. Let $V=E=\omega$ (so $E$ consists of all the initial segments of $\omega$). A subgraph $(V,E_0)$ is connected iff $E_0$ is infinite, so there is no minimal connected subgraph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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