MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Title asks length at most 3, body asks length at most 2. Please edit for consistency. – Gerry Myerson Aug 15 '12 at 23:19
The confusion between 2 and 3 makes it incomprehensible. – Brendan McKay Aug 16 '12 at 3:40
There's also room for confusion as to whether the "length" of a path is the number of vertices or the number of edges. Maybe the two confusions can be made to cancel? I'm pretty sure the OP wants to prohibit paths that have 4 vertices and (therefore) 3 edges. – Andreas Blass Aug 16 '12 at 4:23
up vote 1 down vote accepted

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.

share|cite|improve this answer
It looks promising. Also, I added some comments to my answer which you might find useful. Thanks for the problem. You might ask if weaker versions of set theory allow you to do this. Gerhard "After This Question, More Await" Paseman, 2012.08.16 – Gerhard Paseman Aug 16 '12 at 18:39

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

share|cite|improve this answer
One thing to watch for in the limit is that a vertex may get degree 0. When that happens, you can add an edge back, but you have to keep track and make sure your path condition is not locally undone. Gerhard "Takes Some And Leaves Some" Paseman, 2012.08.15 – Gerhard Paseman Aug 15 '12 at 20:34
Thanks for input! If I understood your algorithm correctly, I think it could produce a vertex of degree 0 even in the countably infinite case. Say I have a star with $\omega$ rays consisting of two edges and the algorithm processes the "middle" vertices of the rays first. Then I end up with the middle vertex of the star disconnected. For the correcting step, I think that similar star graph with rays of length 3 and suitable numbering of vertices would get lead to situation, where you cannot add any edge connecting the center back without creating a path of length 3. – Fred.Fred Aug 16 '12 at 8:30
Indeed, assuming Choice, there is a transfinite version of the above. I suspect being able to do so is equivalent to AC. Theidea is to add back edges to lower labeled pint in a small way, and remove an edge afterwards in case there is a long path. But I need to sleep. Gerhard "Perhaps Clarity Comes With Morning" Paseman, 2012.08.16 – Gerhard Paseman Aug 16 '12 at 8:36
Sorry Fred. I see your comment but my eyes are blurry. Will read it sooon. Gerhard " Really Must Go To Sleep" Paseman, 2012.08.16 – Gerhard Paseman Aug 16 '12 at 8:37
Indeed, morning plus caffeine show my transfinite extension to be flawed. I think Fred has the right take on it, as it seems ugly and problematic to take an approach like mine or like Aaron's initial attempt. Gerhard "Ask Me About System Design" Paseman, 2012.08.16 – Gerhard Paseman Aug 16 '12 at 18:29

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.

share|cite|improve this answer

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$.

share|cite|improve this answer
I am concerned that there will still be an isolated vertex in the limit because it is connected to uncountably many vertices with label 1, and it "never gets its turn." Perhaps you can tell me more about when such a vertex will be processed? (Basically I am worried about the no leaf process continuing infinitely often and affecting a certain unfortunate vertex.) Perhaps this combined with a well ordering argument might work? Gerhard "Ask Me About System Design" Paseman, 2012.08.15 – Gerhard Paseman Aug 16 '12 at 5:13
Yes, that is a problem. I'll think about it. I wonder if one can remove a maximal non-disconnecting set of edges to get a tree and then take it from there. – Aaron Meyerowitz Aug 16 '12 at 7:02
Here is something to think about. Use your same construction iin both cases. In the leafless case, you end up with many stars as well as some with longer branches. The result should be an possibly infinite tree with maximal path length 4, since you added back some edges. Now run your algorithm again on that infinite tree. Gerhard "Hope THIS Makes It Work" Paseman, 2012.08.16 – Gerhard Paseman Aug 16 '12 at 7:07
Also, in the leaf case, how do we get only stars and not, say bipartite graphs with cycles? Gerhard "Back To The Stick Figures" Paseman, 2012.08.16 – Gerhard Paseman Aug 16 '12 at 7:13
I think you have a nice reduction of the problem to bipartite graphs. It might be time to read what Igor Rivin suggested. Gerhard "Ask Me About System Design" Paseman, 2012.08.16 – Gerhard Paseman Aug 16 '12 at 7:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.