Does every 3-valent planar graph admit a maximal tree, which is non-branching?

54 Views Asked by At

Consider a $3$-valent (multi)graph without loops, i.e. multiple edges are allowed, but there are no edges starting/ending at the same vertex. Furthermore, lets assume $\gamma$ is planar, which means that it can be drawn in such a way that there are no crossing of edges. Is it possible to choose a maximal tree inside $\gamma$ (=a non-cyclic subgraph touching all vertices), which itself is non-branching, i.e. only includes 2-valent vertices (+ two 1-valent vertices, i.e. the starting and ending points of the tree)?

I think the answer to this question is positive, as I can not find any counter example, but I have a hard time proving it...

In addition, if the answer is yes, is it possible to choose it such that the starting and end point of the tree are separated only by a single edge, i.e. they are the source and target vertices of some edge in the graph not belonging to the tree?

1

There are 1 best solutions below

1
On BEST ANSWER

The 3-regular planar graph below does not have a spanning path. To see this, note that the spanning path can enter the red vertex through one edge, and leave through another. This leaves a `branch' (i.e., a component of the graph formed by removing the red vertex) that any spanning path does not visit.

enter image description here