Skip to main content
MathOverflow

Return to Question

added 12 characters in body; edited title; added 70 characters in body; added 4 characters in body
Source Link
Fred.Fred
Fred.Fred
  • 409
  • 3
  • 9

Subset of edges of graph touching all vertices with no pathsuch that all paths consist of length more than 3at most two edges

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

Subset of edges of graph touching all vertices with no path of length more than 3

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 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 ?

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

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

Source Link
Fred.Fred
Fred.Fred
  • 409
  • 3
  • 9

Subset of edges of graph touching all vertices with no path of length more than 3

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 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 ?