Problem A. 866. (December 2023)
A. 866. A graph is called 2-connected, if after deleting any point (and the edges adjacent to it) from the graph it remains still connected.
Is it true that in any 2-connected graph with a countably infinite number of vertices it's always possible to find a trail that is infinite in one direction (i.e. a sequence of not necessarily distinct points \(\displaystyle v_1, v_2,\ldots\) such that \(\displaystyle v_i\) and \(\displaystyle v_{i+1}\) is always connected with an edge, and all edges \(\displaystyle (v_i,v_{i+1})\) are distinct from each other)?
Submitted by Balázs Bursics and Anett Kocsis, Budapest
(7 pont)
Deadline expired on January 10, 2024.
The statement is true. Let the original graph be \(\displaystyle G\), and let \(\displaystyle F\) be an arbitrary spanning tree in \(\displaystyle G\). If all vertices have a finite degree in \(\displaystyle F\), then we are can find an infinite path using Kőnig's lemma.
So suppose that \(\displaystyle F\) has a vertex with an infinite degree, let \(\displaystyle v\) denote one such vertex. It is clear that it is enough to find infinitely many edge-disjoint cycles passing through \(\displaystyle v\). Furthermore, if path \(\displaystyle p=(v_1,v_2,...,v_k)\) is given, it is enough to find infinitely many cycles all containing \(\displaystyle p\), and sharing no edge apart from the edges of \(\displaystyle p\): indeed, this means that there are infinitely many edge-disjoint trails between \(\displaystyle v\) and \(\displaystyle v_k\), and these can be combined to an infinite trail.
If we take out vertex \(\displaystyle v\) from tree \(\displaystyle F\), we will ge infinitely many components: let's call them \(\displaystyle v\)-components. We will call two \(\displaystyle v\)-components adjacent, if it is possible to find one vertex in each that is connected with an edge in \(\displaystyle G\). Notice that because of the condition of \(\displaystyle G\) being 2-connected, every \(\displaystyle v\)-component has something adjacent to it.
First assume that every \(\displaystyle v\)-component has only finitely many \(\displaystyle v\)-components adjacent to it. In this case we can find infinitely many edge-disjoint cycles through \(\displaystyle v\) with the following algorithm: let's assume we have already found cycles \(\displaystyle C_1\), \(\displaystyle C_2\),..., \(\displaystyle C_k\). We will show another cycle that is edge-disjoint from these. Cycles \(\displaystyle C_1\), \(\displaystyle C_2\),..., \(\displaystyle C_k\) contain finitely many vertices, thus they intersect finitely many \(\displaystyle v\)-components, and by our assumption these have finitely many adjacent \(\displaystyle v\)-components. Thus we can find \(\displaystyle v\)-component \(\displaystyle A\) which is disjoint from the cycles and is not adjacent to a \(\displaystyle v\)-component intersecting a cycle. Let \(\displaystyle B\) be a \(\displaystyle v\)-component that is adjacent to \(\displaystyle A\). We can find vertices \(\displaystyle a\) in \(\displaystyle A\) and \(\displaystyle b\) in \(\displaystyle B\) such that \(\displaystyle a\) and \(\displaystyle b\) are connected with an edge in \(\displaystyle G\), and now we get a new edge-disjoint cycle by travelling from \(\displaystyle v\) to \(\displaystyle a\) in \(\displaystyle F\), then from \(\displaystyle a\) to \(\displaystyle b\) and finally back to \(\displaystyle v\) from \(\displaystyle b\). Thus we can find infinitely many edge-disjoint cycles thorugh \(\displaystyle v\).
So now we can assume that there exists \(\displaystyle v\)-component \(\displaystyle A\) that has infinitely many adjacent \(\displaystyle v\)-components. Let \(\displaystyle v_1\) be the vertex in \(\displaystyle A\) that is adjacent to \(\displaystyle v\) in \(\displaystyle F\). If we take out vertex \(\displaystyle v_1\) from \(\displaystyle F\), we will get components. Let's those components \(\displaystyle v_1\)-component that do not contain \(\displaystyle v\). Let's call a \(\displaystyle v_1\)-component and a \(\displaystyle v\)-component different from \(\displaystyle A\) adjacent, if they are connected through an edge in \(\displaystyle G\).
If we can find infinitely many \(\displaystyle v\)-components that are connected to \(\displaystyle v_1\) through an edge, we can find infinitely many cycles containing edge \(\displaystyle (v,v_1)\), that do not share an edge apart from this one, so we are done. If this is not the case, \(\displaystyle v_1\)-components have finitely many \(\displaystyle v\)-components in total that are adjacent to them.
If every \(\displaystyle v_1\) component has finitely many \(\displaystyle v\)-components adjacent to them, then there are infinitely many \(\displaystyle v_1\) components. In this case we can find infinitely many cycles containing \(\displaystyle (v,v_1)\) arnd sharing no other edges, similarly to what we have done earlier. The only difference is that it is not guaranteed that every \(\displaystyle v_1\)-component is adjacent to \(\displaystyle v\)-component, however, this is not a problem, since it is enough that they have infinitely many components adjacent to them. If we have already found cycles \(\displaystyle C_1\), \(\displaystyle C_2\),..., \(\displaystyle C_k\), then there are finitely many \(\displaystyle v_1\)-components intersecting cycle \(\displaystyle C_i\), and they have finitely many \(\displaystyle v\)-components adjacent to them, thus there exists \(\displaystyle v_1\)-component which has a \(\displaystyle v\)-component adjacent to it such that no cycle intersects any of them, and using these we can find cycle \(\displaystyle C_{k+1}\). Thus we are also done in this case.
If there exists \(\displaystyle v_1\) component that is adjacent to infinitely many \(\displaystyle v\)-components, then let \(\displaystyle A_2\) be such a component, and let \(\displaystyle v_2\) be the vertex in \(\displaystyle A_2\) that is adjacent to \(\displaystyle v_1\) in \(\displaystyle F\).
We can continue this process inductively. If we have already defined vertices \(\displaystyle v\), \(\displaystyle v_1\),..., \(\displaystyle v_k\), where \(\displaystyle v_k\) is a vertex adjacent to \(\displaystyle v_{k-1}\) in a \(\displaystyle v_{k-1}\)-component that is adjacent to infinitely many \(\displaystyle v\)-components, then we can define \(\displaystyle v_k\)-components as those components we get from \(\displaystyle F\) by taking out vertex \(\displaystyle v_k\) not containing \(\displaystyle v_{k-1}\). WE can define adjacency between a \(\displaystyle v_k\)-component and a \(\displaystyle v\)-component different from \(\displaystyle A_1\). Let \(\displaystyle p\) denote path \(\displaystyle (v_1,v_2,...,v_k)\). If \(\displaystyle v_k\) is connected to infinitely many \(\displaystyle v\)-components through an edge, then we can find infinitely many cycles containing \(\displaystyle p\) and sharing edges only from \(\displaystyle p\). Otherwise, \(\displaystyle v_k\)-components have infinitely many adjacent components in total. If every \(\displaystyle v_k\)-component has finitely many adjacent \(\displaystyle v\)-components, then we can find infinitely many cycles containing \(\displaystyle p\) and sharing edges only from \(\displaystyle p\). And if there is \(\displaystyle v_k\)-component \(\displaystyle A_{k+1}\) that has infinitely many adjacent \(\displaystyle v\)-components, we can define \(\displaystyle v_{k+1}\) and carry on with the inductive process.
If we never get stuck, we have found infinite path \(\displaystyle v\), \(\displaystyle v_1\), \(\displaystyle v_2\), ... in \(\displaystyle F\). Otherwise, we will find the infinite trail in the step where we got stuck using the cycle-method.
Statistics:
18 students sent a solution. 7 points: Czanik Pál, Duchon Márton, Holló Martin, Szakács Ábel, Tarján Bernát, Varga Boldizsár, Wiener Anna. 2 points: 4 students. 1 point: 1 student. 0 point: 6 students.
Problems in Mathematics of KöMaL, December 2023