Idea Cultivation Workshop¶

Solution¶

The square eraser does not harm two properties.

1. Graph connectivity is preserved.

2. It will always have an odd cycle.

Perhaps the second point is a bit harder to grasp. You probably initially guessed that the answer should be \(n-1\) (due to the first property), but no matter how you use the square eraser, a troublesome cycle remains!

For the second property, first note that since \(n \geq 3\), we certainly have an odd cycle initially. Suppose we removed edge \(AB\) from square \(ABCD\), and the odd cycle we had in the previous step was eliminated. Now, traverse the previous odd cycle, but instead of using edge \(AB\), use walk \(ACDB\). It's clear that we will eventually reach an odd walk, and as we said in Chapter 1, every odd walk contains an odd cycle!

From the two points mentioned, we can conclude that due to graph connectivity, we must have at least \(n-1\) edges. And since if we have exactly \(n-1\) connected edges, we have a tree that does not have an odd cycle, we must therefore have at least \(n\) edges.

We leave the construction of an example with exactly \(n\) edges to the reader!

Solution¶

To solve the problem, we use the fact that the GCD of any two consecutive numbers is 1.

Start executing DFS from an arbitrary vertex. Assign the number 1 to the first edge we see, 2 to the second edge we see, and so on. What does 'seeing an edge' mean? Suppose we are at vertex \(u\) and performing DFS. We look at the list of all adjacent edges to \(u\) in order. When we reach edge \(uv\), if no number has been assigned to this edge before, we assign one. Then, if vertex \(v\) is unvisited, we call dfs(v).

So, the number we assign to each edge is its order of being visited. The GCD of the numbers of edges adjacent to the root is 1, because the first edge we traverse is 1 and it's adjacent to the root. For any non-root vertex like \(u\), the GCD of adjacent numbers to \(u\) is 1, because if we entered \(u\) via an edge numbered \(x\), according to the recursive logic of DFS, we will immediately write the number \(x+1\) on one of the edges adjacent to \(u\) (unless the degree of vertex \(u\) is 1, in which case we have no specific constraint on this vertex).

Note that because of the DFS structure, each backedge, which is not part of the tree edges, is seen from its lower vertex! (Why?) Therefore, no problem arises for tree leaves whose degree is not 1.

Solution¶

To solve the problem, we use induction. We set the base case to \(n = 2\), for which its correctness is obvious. We root tree \(T\) at an arbitrary vertex and call the lowest leaf \(u\). Assume the parent of the lowest leaf is \(v\). In this case, all children of \(v\) are leaves (Why?). If \(v\) is the root itself, the statement is obvious (since all vertices except \(v\) are leaves). Otherwise, by removing all children of \(v\) that are leaves, we reach a tree \(T'\) with fewer vertices, which has at least 2 vertices and no vertex of degree 2, so the induction hypothesis holds for it. Assume that in this tree, the number of leaves is \(A'\) and the number of non-leaves is \(B'\), and by the induction hypothesis, \(A' > B'\).

Now, add \(v\)'s children back. If it has \(d\) children, then the changes applied to the tree are as follows:

• Vertex \(v\) ceases to be a leaf.

• All children of \(v\) are added to the set of leaves.

So, if we denote the new number of leaves and non-leaves as \(A\) and \(B\) respectively, we have \(A = A' + d - 1\) and \(B = B' + 1\). And since \(d>1\), it still holds that \(A > B\).

Note¶

The problem stated was a classic lemma that helps us in solving some problems. Generally, in some problems, we can compress vertices of degree 2 and eliminate them. This means that if we color all vertices of degree 2 in the tree red, these degree 2 vertices form a number of disjoint paths (Why?). Now, suppose for each path consisting of degree 2 vertices that starts at a vertex like \(A\) and ends at a vertex like \(B\), we remove this path and only leave an edge from \(A\) to \(B\). After performing these operations, all degree 2 vertices are eliminated, and the overall structure of the tree is preserved. Now, if the tree in the problem is such that the number of leaves is small, we can conclude that the total number of vertices in the tree is also small!

Solution¶

If we didn't know we should think of BFS, how difficult would this question be?

Now, run BFS from an arbitrary vertex. The graph is now partitioned into several layers, where the edges of the graph are either within a single layer or between two adjacent layers.

We claim that the subgraph consisting of the vertices of each layer is bipartite. Assume for contradiction that we have a layer that is not bipartite. Then it must contain an odd cycle. Now, if you remove the layers of this odd cycle, according to the problem statement, the graph should become disconnected, but we know this doesn't happen! This is because the graph is connected by the edges of the BFS tree, and the edges of the BFS tree are only between adjacent layers.

Thus, we proved that each layer is bipartite. So, we can color each layer with two colors such that adjacent vertices have different colors. Now, color the odd layers with colors 1, 2 and the even layers with colors 3, 4. No problem arises because two vertices that have the same color are either within the same layer (where we resolved the issue with bipartiteness) or are not in adjacent layers (meaning there is no edge between them).

It's that simple!