1
$\begingroup$

Let $G=(V,E)$ be an infinite, simple, undirected graph, such that for all $v\in V$ we have $\text{deg}(v) \geq \aleph_0$. Given an integer $k\geq 1$, is there always $E^{(k)}\subseteq E$ such that $(V, E^{(k)})$ is $k$-regular, that is, every vertex has exactly $k$ neighbors?

$\endgroup$

1 Answer 1

2
$\begingroup$

The complete bipartite graph $K_{\aleph_0,\aleph_1}$ does not contain a $k$-regular spanning subgraph for any positive integer $k$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .