Road Cover
In a small town, there are roads between junctions and the road network looks like this:
The mayor wants to place traffic police posts in these junctions in the following way:
- Every road must be incident on at least one junction in which there is a traffic police post.
- The number of traffic police posts must be as few as possible.
The mayor makes the following reasoning:
Because junction 3 is incident on the maximum number of roads, I must place a traffic police post on junction 3 to minimize the number of traffic police posts.
Is he correct?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
If you put a post on junction number 3, each subjunction (those adjacent to #3) must have at least 1 post. However, the post in #3 may not be necessary. Therefore, only 4 post is required.