5
$\begingroup$

Let $G=(V,E)$ be a graph with minimum degree $\delta(G)=n\lt\aleph_0$. Does $G$ necessarily have a spanning subgraph $G'=(V,E')$ which also has minimum degree $\delta(G')=n$ and is minimal with that property?

This question is easily answered in the affirmative if $G$ is locally finite or if $n\le1$. It already seems difficult for $n=2$, but I am not very clever and may be missing something obvious.

The question also seems to make sense for hypergraphs:

Let $m,n\in\mathbb N$. Let $E$ be a family of sets, each of cardinality at most $m$. If $E$ is an $n$-cover of a set $V$ (each element of $V$ is in at least $n$ elements of $E$), does $E$ contain a minimal $n$-cover of $V$?

I would expect such simple questions to have been asked and answered 100 years ago.

Where are these questions considered in the literature?


P.S. The following proof for the simple case of a (non-hyper) graph with $\delta=1$ is probably a dead end, as it does not seem to generalize in any obvious way. I'm putting it here anyway because it's quite simple.


Theorem. A graph with no isolated points has a minimal spanning subgraph with no isolated points.


Proof. Let $G$ be a graph with no isolated points. Let $H$ be a maximal spanning subgraph of $G$ not containing $K_3$ or $P_4$ as a subgraph, induced or otherwise. Then $H$ is a star-forest, possibly with some isolated points. For each isolated vertex $v$ of $H$, choose an edge of $G$ which is incident with $v$ and add it to $H$. This results in a spanning subgraph of $G$ in which each component is a nontrivial tree of radius at most $2$.The proof is completed by observing that any nontrivial tree of radius at most $2$ has a minimal spanning subgraph with no isolated points.

$\endgroup$
10
  • 2
    $\begingroup$ Is there a point to writing $n < \aleph_0$ instead of $n \in \mathbb{N}$? $\endgroup$ Mar 3, 2019 at 7:20
  • 1
    $\begingroup$ for hypergraphs and 1-cover this is written in the answer by Taras Banakh here mathoverflow.net/a/308417/4312 $\endgroup$ Mar 3, 2019 at 16:07
  • $\begingroup$ @FedorPetrov Thanks for finding that! I guess Taras Banakh's argument can be generalized to prove that for any function $f:V\to\omega$ and any $f$-admissible hypergraph with edges of bounded finite size, there is a minimal $f$-admissible subhypergraph? Let's see, start by finding a maximal set of edges which does not cover any vertex $v$ more than $f(v)$ times . . . $\endgroup$
    – bof
    Mar 3, 2019 at 16:54
  • $\begingroup$ that is what I started to type but realized both some difficulties and that my flight is within two hours:) $\endgroup$ Mar 3, 2019 at 17:01
  • $\begingroup$ Ah, now it again seems that everything works. Take such set of edges $E_1$. Let $U$ be the set of vertices $v$ covered by $E_1$ exactly $f(v) $ times. All (well, non-empty) edges intersect $U$. So by induction proposition we have a minimal covering $E_2$ of $V\setminus U$. Let $U_1=U\setminus \cup E_2$. Take $E_2$ and all edges if $E_1$ which have something from $U_1$. It remains to minimally cover $U\setminus U_1$ by remaining edges of $E_1$, and the covering function of all vertices strictly decreases. $\endgroup$ Mar 3, 2019 at 18:28

1 Answer 1

2
$\begingroup$

Fedor Petrov pointed out in a comment that the hypergraph question for $n=1$ was settled nicely by Taras Banakh in his answer to Dominic van der Zypen's question Minimal covers in hypergraphs with finite edges, and he mentioned some ideas for generalizing Banakh's argument to $n$-covers. This is my attempt to answer the general question in the affirmative using the ideas of Banakh and Petrov.

In order for the induction to work, it seems necessary to work with multihypergraphs (hypermultigraphs?) instead of simple hypergraphs. Therefore I will consider a hypergraph as a triple $H=(V,E,I)$ consisting of a vertex set $V$, an edge set $E$, and a vertex-edge incidence relation $I\subseteq V\times E$. For any vertex $v\in V$, let $E_v=\{e\in E:(v,e)\in I\}$, the set of all edges incident with $v$. For any edge $e\in E$, let $V_e=\{v\in V:(v,e)\in I\}$, the set of all vertices incident with $e$.


Banakh–Petrov Theorem. Consider a hypergraph $(V,E,I)$. Let $m\in\omega$ and $\varphi:V\to\omega$ satisfy the conditions: $$\forall e\in E\ |\{v\in V_e:\varphi(v)\gt0\}|\le m;$$ $$\forall v\in V\ |E_v|\ge\varphi(v).$$ Then there is a set $E'\subseteq E$ such that: $$\forall v\in V\ |E'\cap E_v|\ge\varphi(v);$$ $$\forall e\in E'\ \exists v\in V_e\ |E'\cap E_v|=\varphi(v).$$


Proof. We use induction on $m$. The case $m=0$ is trivial, so we assume that $m\gt0$ and that the theorem holds with $m$ replaced by $m-1$. We may assume without loss of generality that $\varphi(v)\gt0$ for all $v\in V$.

By Zorn's lemma there is a set $D\subseteq E$ which is maximal with the property that $\forall v\in V\ |D\cap E_v|\le\varphi(v)$.

We will apply the induction hypothesis to the hypergraph $(V,F,J)$ where $F=E\setminus D$ and $J=I\cap(V\times F)$, and the function $\psi:V\to\omega$ defined by setting $\psi(v)=\varphi(v)-|D\cap E_v|$.

First, if $e\in F$, then by the maximality of $D$ there is a vertex $v\in V_e$ such that $|D\cap E_v|=\varphi(v)$. Hence $\psi(v)=0\lt\varphi(v)$, so that $|\{v\in V_e:\psi(v)\gt0\}|\le|\{v\in V_e:\varphi(v)\gt0\}|-1\le m-1$.

Second, if $v\in V$, then $|D\cap E_v|+|F\cap E_v|=|E_v|\ge\varphi(v)$, so that $|F\cap E_v|\ge\varphi(v)-|D\cap E_v|=\psi(v)$.

Therefore, by the inductive hypothesis, there is a set $F'\subseteq F$ such that $$\forall v\in V\ |F'\cap E_v|\ge\psi(v)=\varphi(v)-|D\cap E_v|;$$ $$\forall e\in F'\ \exists v\in V_e\ |F'\cap E_v|=\psi(v)=\varphi(v)-|D\cap E_v|.$$

Let $C=D\cup F'$; then we have $$\forall v\in V\ |C\cap E_v|\ge\varphi(v);$$ $$\forall e\in F'\ \exists v\in V_e\ |C\cap E_v|=\varphi(v).$$

Let us call a subset $S\subseteq D$ bad if $|(C\setminus S)\cap E_v|\lt\varphi(v)$ for some $v\in V$, good otherwise. Since $D\cap E_v$ is finite for each $v\in V$, every bad subset of $D$ contains a finite bad set. Therefore, by Zorn's lemma, there is a maximal good set $S\subset D$. The set $E'=C\setminus S$ has the desired properties.

$\endgroup$
3
  • $\begingroup$ Ah, what remains is locally finite! Nice. But I wonder whether this holds for infinite function $f$. $\endgroup$ Mar 4, 2019 at 15:43
  • $\begingroup$ @FedorPetrov If $f(v)$ is infinite for all $v$ how could there possibly be a minimal $f$-admissible graph? (I am not considering non-choice worlds where the cardinality of an infinite set can be changed by adding or removing one point.) But I suppose you are considering the possibility that there may be something interesting to say about functions that take some infinite values. Personally, my curiosity about this topic is satisfied for now, except for the question that remains unanswered: Is there a classical reference for this stuff? $\endgroup$
    – bof
    Mar 4, 2019 at 15:56
  • $\begingroup$ Say, may we get smth like "any remained edge which contains a vertex with finite $f$ can not be removed"? I suggest to ask Taras Banakh directly. Or possibly Peter Komjath. $\endgroup$ Mar 4, 2019 at 19:34

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.