Project 3: Bridges and Walking Tours

We are going to play a game creating walking tours of cities with bridges.  We begin in the city of King’s Mountain, which is built on four land masses – both shores of a river and two islands in midstream – connected by a total of seven bridges (shown in green).

EXAMPLE 1:  Can you create a walking tour of the city that crosses every bridge exactly once?  You can begin anywhere you like, and end anywhere you like, as long as you cross each bridge just once.

Background – Graph Theory

We can simplify the picture of King’s Mountain to make it easier to deal with:

The key elements of the map are the four land masses (let’s label them A, B, C, and D) and the seven bridges (p,q,r,s,t,u and v) (thanks to for the images):

For the purposes of our problem, we can simply think about each land mass as a point (A, B, C, and D), and the bridges as lines connecting the points (p,q,r,s,t,u and v) – like this:

We call this kind of picture a graph – the points are called vertices and the the lines are called edges.  Our goal of finding “a walking tour that crosses each bridge once” is now matter of tracing out all the edges without lifting our pencil (and without repeating any edge).


Assignment, Due TUESDAY 10/28 (end of day)

Warm up (This Warm Up is just for practice – you do NOT need to submit your answers – see below for the three-part Assignment to be submitted).  The following  examples build on EXAMPLE 1:

EXAMPLE 2: If you are given the freedom to build one new bridge in King’s Mountain (“make one new edge in the graph”), can you do it in such a way the walking tour becomes possible?  Do it!

EXAMPLE 3: If you are given the freedom to destroy one bridge (“erase one edge”), can you do it in such a way that the walking tour becomes possible? Do it!

EXAMPLE 4: Construct walking tours for each of the following graphs (or decide if it is impossible).

Assignment.  Your assignment has 3 parts.

PART 1.  Leave a comment responding to EXAMPLE 4 (above), telling us for each one of the 8 graphs whether a walking tour is possible or not.  You only have to state whether it is possible or impossible for each one.

PART 2.  Challenge your friends:  Now it’s up to you to build your own graph, and challenge your classmates to construct a walking tour (or to determine if it is impossible).  It can consist of as many points as you wish, and as many bridges (edges) connecting them.  When you’re finished, decide for yourself if a walking tour crossing each bridge exactly once is possible.   Remember, the most challenging puzzles are the ones where the answer is difficult to determine. Post two puzzles in the comments.  See the note  “POSTING YOUR PUZZLE ONLINE” below for instructions on how to draw and share graphs online.

PART 3.  The third part of your assignment is to write a short paragraph (at least 3 sentences) responding to the following prompt.  Be sure to respond to each part:

Writing Prompt:  Did you enjoy this assignment? Why or why not?  Describe a connection between this assignment and our work in the class.  (If you don’t believe there is a connection, try to imagine why we are doing this).  Leave your response in the comments.

POSTING YOUR PUZZLE ONLINE.  I recommend the site – it allows you to draw something, then click “SHARE” and get a link to your drawing.  You can post the link in a comment, and we’ll be able to click on it and view your drawing.   Don’t worry if it’s not pretty!  For example, here is a graph that I drew (can you find a walking tour that crosses all edges?):



11 thoughts on “Project 3: Bridges and Walking Tours

  1. 1 YES
    2 YES
    3 NO
    4 NO
    5 YES
    6 YES
    7 YES
    8 YES
    PART 2
    There is at least one possible way.

    PART 3 I was certainly a good assignment because I was having fun doing it. However, it took longer than I think. It helps me to think logically. For example, I have to remember which one way I have been use.

    1. Thanks, SinFong! I like your puzzle a lot. You’re right, keeping track of your solution is a challenge (I like to print the puzzles out & trace over them with a red pen…). (Don’t forget to submit one more for full credit – the instructions say to post two puzzles.)

  2. I agree with SinFong for the bridges as follows:
    1- yes
    2- yes
    3- no
    4- no
    6- yes
    8- yes

    I enjoyed this assignment a lot. As a kid I was challenged by a camp counselor to draw a set of shapes without lifting the pen from the page, one of those shapes was map 7/8. I believe this kind of analysis of ordered commands to create a whole is useful to proofs. You see the whole statement and you have to pick apart the pieces in the correct order to give you your proof. Sometimes you can do steps out of order and sometimes you cant. The complexity of selecting parts and ordering them is illustrated here in this exercise.

  3. The overall game of position machines has evolved in to an international trend with casinos all around the earth giving many different incentives and bonuses to players of every caliber. There are many online casinos that providing “game reset” bonuses to their slot players, wherein people might profit any bonuses they have gained on position machines situated in different nations, for example, a person may get dual the bonus money if he or she may money in bonus gained on an Irish casino. Furthermore, some on line casinos present people “points” system whereby a particular quantity of advantage points might be accumulated. These bonus items may then be redeemed for a variety of goods and services.

  4. The existing US Eagles team is made up of a collection of promising young Players Many of them never performed a game of rugby, even although they had the chance. But it surely these avid gamers are an exciting blend of Strength Staying power skill, attitude, and choice that has produced a very strong team.

  5. This is likely one of the reasons that online shopping turn into so regularly occurring throughout the 2021 holiday season. When the store hours started at 7 p.m. on Thanksgiving Day, there were still tons of Valued clientele They knew that they could start shopping early in the morning on Black Friday. Because retailers started offering discounts and specials early on, people were in a better position to buy gifts and items at the right price. The gross sales were still slow moving, but not as slow as the following day after Thanksgiving, the official day after the holiday, when millions of clients tried to beat the crowds to the malls.

  6. The quantity of this wager can be established to fit any team’s needs. There is no question that people can allow gambling take control of them top them down a terrible street. We don’t even attempt to be that way, we just are.

Leave a Reply

Your email address will not be published. Required fields are marked *