Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A water company lays pipes as a tree: every junction is joined to the network, and there are no loops. Four junctions have pipes each, two junctions have pipes each, and every other junction is an end point with pipe.
Find the number of end points (leaves) and the total number of junctions. Use the fact that a tree with vertices has edges, and check your answer by the degree sum.
A tree on vertices has edges; a forest with components has . Bipartite means no odd cycle; with no triangle, . A connected graph has an Euler circuit when all degrees are even, and an Euler trail when exactly two are odd.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. Vertices. .
Step 2. Degree sum. .
Step 3. Solve. , so and .
Check. junctions, pipes, degree sum .
Answer: end points and junctions.
Log in to join the discussion.
Loading…