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


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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