Skip to main content
added 445 characters in body
Source Link
Fred.Fred
  • 409
  • 3
  • 9

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.

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. Thanks for every comment.

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.

Source Link
Fred.Fred
  • 409
  • 3
  • 9

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. Thanks for every comment.