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?

  • 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 Paseman Jul 21 '18 at 18:22

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.

| cite | improve this answer | |
  • $\begingroup$ I guess you mean to do this separately in each connected component. $\endgroup$ – Joel David Hamkins Jul 21 '18 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$ – Aaron Meyerowitz Jul 21 '18 at 19:57
  • $\begingroup$ Yes. Each component $\endgroup$ – Mike Jul 21 '18 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$ – Mike Jul 21 '18 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$ – Joel David Hamkins Jul 21 '18 at 20:06

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.

| cite | improve this answer | |
  • $\begingroup$ No, I misunderstood. $\endgroup$ – Aaron Meyerowitz Jul 21 '18 at 21:36

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.