Subset of edges of graph touching all vertices such that all paths consist of at most two edges

Question

Let $G=(V,E)$ be a (simple) finite graph such that every vertex has degree at least 1. Then it is easy to see that there is a subset $E'$ of $E$ such every vertex in $G'=(V,E')$ still has degree at least 1 and all paths (with no repeating edges) in $G'$ are of (edge-wise) length at most 2. (I just keep removing middle edges of paths of length 3 until I'm done.) My question is, does this hold for infinite graphs ?

EDITED: tried to make the question more clear, as comments suggested

Answer 1

Aaron Meyerowitz suggested to try to reduce the problem to trees and, to me, this seems to work. First we can suppose that $G$ is a connected graph, because we can solve the problem separatly for each component. It is easy to see by Zorn's Lemma, that every connected graph contains a spanning tree, i.e. a subgraph which is a tree and which connects all vertices of the original graph. Hence it is enough to solve the problem for a tree.

Put $E_0=\emptyset$. We choose a root $r$ of the tree and denote by $L_n$ the set of vertices which are $n$ edges far from $r$. By hypothesis, $L_1$ is nonempty. If $L_1$ contains at least one vertex of degree 1, we define $E_1$ to be exactly the edges connecting $r$ with the vertices from $L_1$ of degree 1. Otherwise, we pick arbitrary $x_1$ from $L_1$ and define $E_1$ as a singleton consisting just of the edge connecting $r$ and $x_1$. Now we continue inductively by level $n$ of the tree (which is easily well-defined). Let $v \in L_n$, put $E_n=E_{n-1}$:

• If $v$ is leaf, i.e. the tree "under" $v$ has just one vertex, do nothing.
• If there is an edge from $v$ to an element in $L_{n-1}$, add to $E_n$ all edges connecting $v$ with leaves under $v$.
• Otherwise, apply to $v$ the same procudere as to $r$ (if there is a leaf under $v$, add all the edges connecting $v$ with leaves to $E_n$, otherwise pick some edge and add it to $E_n$).

Put $E'=\bigcup E_n$, this (I think) is the desired subset of edges, since:

Let $v$ be a vertex, then $v \in L_n$ for some $n \geq 0$.

• $\operatorname{deg}v \geq 1$: Suppose there is no edge connecting $v$ with any edge from level $n-1$. Then by the construction there must be an edge from $v$ to some vertex in level $n+1$.

• Suppose $v$ has degree 1. Then by the construction, the parent of $v$ is connected only to vertices of degree $1$. Thus there is no path of edge-wise length more then 3.

Thanks for every comment.

Answer 2

You should be able to do something similar, at least for graphs with a bijection to the natural numbers. Using the bijection, take the next unprocessed vertex. If it is of degree one, move on. If it has any neighbors of degree one, remove all other edges to neighbors of degree not 1, making a disconnected star. Otherwise remove all edges incident to the vertex except for the edge leading to the smallest numbered vertex. A trans-countable version of this may also work, but you will have to come up with the limit case.

Gerhard "Ask Me About System Design" Paseman, 2012.08.15

Answer 3

This is not really an answer, but I conjecture that the issues are very closely related to the issues which arise in the case where you are asking for for paths to have lengths not exceeding 1, in other words, a perfect matching. There are fairly subtle issues which come up, but if you read Ron Aharoni's 1991 paper, you will gain enlightenment.

Answer 4

I think so. here is an incomplete approach which I had thought would answer the question constructively based on distance from a vertex or set of vertices:

Call two vertices connected if there is a finite path between them. The graph consists of one or more connected components. It is enough to prove the result for a connected graph $G$ having at least 3 vertices. So a vertex may have unaccountably many neighbors, however every pair of vertices has a finite shortest path connecting them.

We can label the vertices of $G$ with non-negative integers and possibly delete some edges subject to:

1. There is a vertex labelled $0.$
2. A vertex labelled $k \gt 0$ has at least one neighbor labelled $k-1.$
3. Vertices connected by an edge have labels which differ by $1.$
4. The graph is still connected.

If there is a leaf, a vertex of degree one, the labeling is unique: All leaves are labelled $0$ and each (other) vertex is labelled with the distance to the closest leaf. Then any edges connecting vertices with the same label are deleted

If there are no leaves then label some starting vertex $s=s_G$ with $0$, then label the others according to distance from $s,$ then delete edges connecting vertices with the same label.

Leaf Case Assume first that $G$ has a leaf. Select all edges labelled $2j,2j+1$. If a vertex labelled $2j$ has no neighbors labelled $2j+1,$ then select a single edge on it labelled $2j-1,2j.$ The result is a collection of single edges and stars with an odd label on the center. (We neglected the trivial but very important case that there are two vertices.) So we are done with this Leaf Case in two steps.

Leafless Case If $G$ has no leaves, then delete all but one edge on $s_G$. This creates no isolated vertices but may create several (even uncountably many) components. The component of $s_G$ has at least one leaf (namely $s_G$). Other vertices in that component may need their labels raised or lowered by $1$. However all edges for that component are handled in two steps. Any other components with leaves need all their labels lowered by 1. However all these components are completely handled in two steps. In any component $H$ with no leaves we pick a starting vertex $s_H$ with label $1$. It's label must be lowered to $0\dots$ unfortunately other labels may increase arbitrarily. I had mistakenly thought that Although there can be (countably) infinitely many stages, the selected and discarded edges for a vertex with initial label $m$ are determined by stage $m+1$.