I have the following graph theory problem:
In a country there are pairs of towns connected by roads in such a
way that you can get from any town to any by those roads. The
president of the country had ordered to build several new towns and
roads so that you could still get from any town to any by
roads. As it turned out, there are now $100$ roads that do not share
ends pairwise, connecting newly built towns to the older ones. Proof
that you can close a number of roads so that there would be
left only a single path between each two of the towns, and also that there
would be no less than $100$ towns that would have only a single road
leading out from them.
I came up with the following:
First, let's translate the problem to the language of graph theory.
Obviously, the towns and roads here are vertices and edges of an undirected graph, let's call it $G$. The "get from any town to any" condition means that $G$ is connected. Next, we make a union with an nonempty set of vertices and edges $U$ such that $G \cup U$ is connected. This graph has $100$ edges each without a common end with one another, and each of those edges connects a vertex from $V(G)$ to a vertex from $V(U)$. What needs to be proven is that this graph has a spanning tree (given by the "single unique path" condition) that has at least $100$ leaves. Such a tree does exist since the graph is connected.
Second, I tried to consider the $100$ edges we have (let's call this edge set $F$). They don't have any ends in common, and each edge is incidental to a vertex $x \in V(G)$ of an arbitrary degree $\geq2$ and a vertex $y \in V(U)$ that is either a leaf vertex (deg. of $1$) or not. If it is a leaf vertex, then we don't need to do anything with it and we just add it to the number of needed leaves for the proof. If it isn't (i.e it has more than one vertex adjacent to it), then we consider two cases: a) $y$ has other leaves adjacent to it; b) it doesn't and each other adjacent vertex is of degree $\geq2$. In the first case, we have one or more leaves found, and in the second case we remove all edges adjacent to $y$ except $xy \in F$ and now it is a leaf itself. Thus, we should be able to attain at least $100$ leaves.
The final wanted condition is that we need the resulting graph to be a spanning tree. I'm not sure if I can just say that next we arbitrarily delete edges to attain it (would that be rigorous enough?), or if we need to construct a Trémaux tree or something along those lines. So, I would like to know if the first part of the solution (about edges and leaves) is sufficient enough for a proof and if it is correct at all, and would also like some help on the second part (about a spanning tree).
Best Answer
You can insist that each edge in $F$ is a leaf vertex: First let $T'$ be a spanning tree of $G$. Then, writing $V(G)=n$, note that $T'$ has $n-1$ edges. Then $T'\cup F$ is the graph you are looking for. Indeed, $T' \cup F$ is connected, because each edge in $F$ has exactly one edge in $T'$. Furthermore, $T' \cup F$ is a graph w $n-1+100$ edges and $n+100$ vertices, so $T' \cup F$ must be a tree. Finally, each of the 100 vertices in $U$ is each incident to exactly one edge in $F$, and none in $T'$ [because $T'$ is a subgraph of $G$ and every edge in $G$ is between two older towns]. So each of the $100$ vertices in $U$ is incident to exactly one edge in $T' \cup F$ and thus must be a leaf. Thus indeed, $T'\cup F$ is a connected graph [every town is reachable from any other], where each of the $100$ towns of $U$ is a leaf, which is what you want.