Suppose $G=(V,E)$ is a simple, undirected graph with $|V|,|E|$ infinite. Is there $B\subseteq E$ with $|B| = |E|$ such that $(V,B)$ is bipartite?
$\begingroup$
$\endgroup$
1
asked Jul 21, 2018 at 18:15
-
4$\begingroup$ Try a spanning tree or forest. If AC holds, V will have as many vertices as E has edges. Gerhard "Simple As A To B" Paseman, 2018.07.21. $\endgroup$– Gerhard PasemanCommented Jul 21, 2018 at 18:22
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
Yes. In each component Take a vertex $v$ and for every vertex $u$ let $d(v,u)$ be the shortest distance in $G$ between $v$ and $u$, where distance is defined as the fewest number of edges. Then every edge $\{u,u'\}$ in $G$ satisfies $|d(v,u)-d(v,u')| \le 1$, and the graph formed from $G$ by removing all edges between vertices $u$ and $u'$ s.t $d(v,u')=d(v,u)$ is bipartite.
-
$\begingroup$ I guess you mean to do this separately in each connected component. $\endgroup$ Commented Jul 21, 2018 at 19:55
-
1$\begingroup$ If there are finitely many components, restrict to an infinite one. If there are infinitely many then ignore the isolated vertices (if any) and take one edge from each other component. $\endgroup$ Commented Jul 21, 2018 at 19:57
-
-
$\begingroup$ It takes a little work to show that the resulting graph $H$ is also infinite: We may assume that an infinite number of vtcs are in components $X$ w 2 or more vertices in $X$; i.e., $\sum_{X; |V(X)| \ge 2} |V(X)|$ is infinite. So $|E(H)|$ is at least $\sum_{X; |V(X)| \ge 2} |V(X)|-1$, which is also infinite $\endgroup$– MikeCommented Jul 21, 2018 at 20:01
-
$\begingroup$ Since E could be uncountable, you can't necessarily just restrict to one component, as they may all be too small. But it seems fine to just do it separately in each component. $\endgroup$ Commented Jul 21, 2018 at 20:06
$\begingroup$
$\endgroup$
1
I initially thought you were asking about the sub-graph induced by the endpoints of $B.$ I suppose then one could simply ask about an infinite set of vertices which induce a subgraph which is bipartite with infinitely many edges.
For that, $K_{\infty}$ is a counterexample More generally, take any finite graph and replace each vertex by a $K_{\infty}$ and each edge by all possible edges between the corresponding components.
The question as asked has been answered. For this modification I wonder what could be said.
We may assume the graph is connected, otherwise there is either an infinite connected component or an infinite number of disjoint connected components each with an edge.
In any case, infinite diameter is enough.
A infinite connected graph of finite diameter has at least one vertex of infinite degree, but that is not always enough.
If the diameter is infinite then there is an infinite path $v_0,v_1,v_2,\cdots$ with $d(v_0,v_i)=i.$ Then the graph induced on $\{v_0,v_1,v_3,v_4,v_6,v_7,\cdots\}$ has all vertices of degree exactly one.
If a graph has diameter less than $2r$ and the maximum degree is $D$ then there are less then $2D^r$ vertices.
Here are some incomplete thoughts on the remaining case: Suppose that $G$ is an infinite connected graph of finite diameter $d$. Then fix a vertex $v$ and let $G_i$ (for $i$ up to the diameter) be the set of vertices at distance $i$ from $v$. We may as well let $v$ have infinite degree. If $G_1$ has an infinite independent set then the induced graph on $v$ and that subset is an infinite star. Otherwise $G_1$ seems like it should have finite dominating set: Any maximal independent subset. More could be said but I will stop there.
answered Jul 21, 2018 at 19:35