OpenLab Assignment – Bridges and Walking Tours

The assignment below is due BEFORE CLASS on Thursday, October 8th (it is essential that you complete it before class, as we will be doing a class activity building on the assignment).

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 Thursday 10/8 (beginning of class)

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

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 4 parts.

PART 1.  For each of the four graphs below (G1 – G4), decide whether it is possible to create a walking tour crossing each bridge exactly once.  Post your solutions here (TO POST A SOLUTION, JUST LIST THE POINTS OF YOUR WALKING TOUR IN ORDER).  If it is not possible to create a create a solution, say so!

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.  You MUST label your points “A, B, C…” etc.  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.  Solve a friend’s puzzle.  Leave a response to a friend’s posted puzzle, giving a solution.  TO POST A SOLUTION, JUST LIST THE POINTS OF YOUR WALKING TOUR IN ORDER.

Here is a puzzle:
Here is a solution: (start at A) – A, B, D, A, E, B, C, E

PART 4.  The last 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 “SAVE” and get a link to your drawing. If you have another (free) solution that you’d like to use, that’s fine! 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?):


  1. Allison Kirshner

    G1 = F-G-H-I-A-B-I-C-H-B-C-D-G-E-F-D-E
    G2 = E-F-A-B-F-C-D-E-B-C
    G3 = A-B-C-D-E-F-G-E-H-G-D-H-I-C-J-B-I-J-A
    G4 = Not possible

  2. Allison Kirshner

    Please see the attached puzzle:

    • Ihn Lee

      1st puzzle A-B-C-D-B-E-F-B-J-K-B-L-M-B-G-H-I-B-H
      2nd puzzle Is there a line between A and D? If not, it is impossible.

  3. Allison Kirshner

    Although I was previously familiar with the “Seven Bridges of Königsberg,” and have enjoyed these puzzles in the past, I find that I quickly get frustrated and impatient with these types of puzzles and want to find out the rule. This assignment relates to our work in class because we were presented with a statement “[t]his puzzle has a solution,” and we have to prove whether that statement is true or false.

  4. Luis lora

    1. G1.G2.G3 Possible G4 Not possible See
    G1. E>F>D>>G>ED>C>H>B>I>IC>CB>A>L>IH>HG>GF
    I very much enjoyed this assignment due to the fact that ive drawn these bridged networks in a previous course . Any time i start one of these in color its always interesting to see the shapes created within the exterior of the over all shape. Sometimes the way the shapes are created may hint to a certain network or bridge that must be connected. I agree with my classmate in regards to working with statements and determining whether they were true or false and if they worked.

    • Allison Kirshner

      Hey Luis. I love how challenging your puzzles are. I worked out the second one. K,L,A,B,K,D,E,F,D,C,L,B,K,F,G,H,I,J,K,H,I,F,K

    • Han Zhang

      I like the puzzles that you create, the first one could be : F-D-C-E-D-C-I-B-H-C-B-A-I-H-G-F
      the second one is no solution .

  5. Christopher Cruz

    G4:no solution

    I love puzzles like this, it was fun and awesome to do. In this course we are asked to find possible solutions for problems we face and we can approach solutions using different routes when possible.

  6. hanzhang

    G1: F-G-D-F-E-G-H-I-C-H-B-A-I-B-C-D-E
    G2: E-B-F-C-B-A-F-E-D-C
    G3: D-G-H-E-G-F-E-D-C-I-B-C-J-C-B-A-J-I-H-D
    G4: unworkable
    1: yes, 2 yes, 3no, 4 no, 5 yes , 6 no, 7 yes, 8 no.
    I am enjoying to do these puzzles and after finish it , I am trying to find some regulations to solve the problem as ” whether there is a route for this puzzle? if not, can we add or substitute something to make it workable?” from several questions we have done, I find out if there is no route , we could add one bridge or deduct one bridge to make it workable.
    I am trying to focus on the following questions: how many points is connected with odd bridges? how many points is connected with even bridges? what is the solution could be?
    if there is a kind of formula, how to prove it ?

    • Irina Chernyavskiy

      G1 = F->G->H->I->A->B->I->C->H->B->C->D->G->E-F->D->E
      G2 = E->F->A->B->F->C->D->E->B->C
      G3 = A->B->C->D->E->F->G->E->H->G->D->H->I->C->J->B->I->J->A
      G4 = Not possible

      I do like his type of problem unfortunately it takes me a lot of time to solve it. As for the link with the course the only thing that I can think of is proving something using properties of even and odd numbers. The puzzles can be solved using those properties.

      This is my puzzle

    • Irina Chernyavskiy

      For your first puzzle the solution is D->B->B->C->A->B->E->D->C->E

    • Jared Cruz

      For the first puzzle, the solution is: D>B>A>C>B>E>C>D>E

  7. Ihn Lee

    G1 E-D-G-E-F-D-C-H-B-C-I-A-B-I-H-G
    G2 E-D-C-B-E-F-A-B-F-C
    G3 G-F-E-H-D-E-G-D-C-I-B-C-J-A-B-J-I-H-G

    I personally don’t like it at first because I am not good at this. After few days I see this post, I still struggle to find the solution. But I didn’t give up and try harder to find it.

    Here is my puzzle!

    • Nina Melendez

      I really enjoyed your puzzle and I think I was able to get a solution

    • Nina Melendez

      I really enjoyed your puzzle and I think I was able to get a solution

    • Nina Melendez

      I really enjoyed your puzzle and I think I was able to get a solution

      • Ihn Lee

        Good job, you are right!

    • Denyese Gonsalves

      For Ihn Lee’s puzzle:
      A-C, D-B, D-C, C-B, B-D, B-A, A-D, D-A,A-B

      • Ihn Lee

        Hi, Denyese. From ‘D-B’ to ‘D-C’, are you going back to D from B? If so, you make more than one trip for one bridge.

  8. Denyese Gonsalves

    G1: E-G, G-D, D-F, F-E, E-D, D-C, C-I, I-B, B-H, H-C, C-B, B-A, A-I, I-H, H-G, G-F
    G2: C-F, F-B, B-E, E-F, F-A, A-B, B-C, C-D, D-E
    G3: E-H, H-D, D-G, G-E, E-F, F-G, G-H, H-I, I-J, J-C, C-I, I-B, B-J, J-A, A-B, B-C, C-D, D-E

    This is my puzzle

    At first, upon reading the assignment instructions I felt that the assignment would be one I would hate. I must say when I started it I enjoyed it thoroughly. I feel that the connection to class deals with set theory especially intersections with regards to unions and intersection.

    • Jack Berner

      I like your puzzle, Denyese. At first I didn’t think there was a solution, but then I realized you can:

      A > E > A >D > A > C > A > B > A > F

  9. Denyese Gonsalves

    This is my puzzle,

  10. Jack Berner

    My puzzle solutions:
    G1: F>E>G>D>F>G>H>C>I>H>B>I>A>B>C>D>E
    G2: C>B>A>F>E>B>F>C>D>E
    G3: E>F>G>D>H>E>G>H>I>C>J>I>B>J>A>B>C>D>E
    G4: No solutions

    I like little brain teasers and puzzles like this, so I was excited to do this assignment. I had to really rely on trial and error to find viable “walking tours” through each of the puzzles, but in the process I think I did notice one pattern that points to a rule for a solution being impossible. It seems to be the case that if a puzzle only has points which are intersected by more “bridges” than the number of other points to which those bridges are connected, then a “walking tour” is impossible. I haven’t exactly proved this to myself and I’m not sure it’s right. I think these puzzles demonstrate that it only takes one of many possible solutions to prove that something has a solution, but that finding a rule for what makes something not possible (ie false) can be a powerful way of determining exactly what makes a thing possible (ie true). In this way I think this activity relates to the way we’ve been talking about logic and to how we’ll be applying that in writing proofs.

    I’ll post my puzzle later on in a separate comment.

  11. Nina Melendez

    PART 1.
    G1- E,G,D,F,E,D,C,I,B,H,C,B,A,I,H,G,F
    G2- C,F,B,C,D,E,B,A,F,E
    G3- E,H,D,G,E,D,C,J,B,I,C,B,A,J,I,H,G,F,E


    PART 3.

    PART 4.
    I did enjoy this assignment; I gravitate towards problem solving and patterns which I could see presented in this activity. For me it relates in that each patterns solution, or lack thereof was because of a logistical tangible reason. Even coming up with a puzzle you had to problem solve and decide if it had a solution or not.

  12. Jared Cruz

    Part I
    G1: F>G>H>I>A>B>I>C>H>B>C>D>E>G>D>F>E
    G2: E>F>A>B>F>C>B>E>D>C
    G3: G>H>I>J>A>B>J>C>I>B>C>D>H>E>D>G>F>E
    G3: It is impossible
    Part III
    Part IV
    I did enjoy the assignment. It really got the brain juice pumping. I noticed that from certain vertices there were either an odd number of possible paths or an even number of possible paths. It seemed to work out, navigating once, when there were an odd number of paths. The assignment may be related to the work we have done on permutations.

  13. Jack Berner

    Here’s my puzzle. It looks really simple, but I think it’s actually kind of tricky.

  14. Jodel Delectable

    G1: F—>G —>H —>I —>B —>A —>I —>C —>B —>H —>C —>D —>F —>E —>D —>G
    G2: C—>F —>A —>B —>C —>D —>E —F —>B —>E
    G3: H—>I —>C —>J —>B —>I —>J —>A —>B —>C —>D —>E —>H —>D —>F —>E —>G —>H
    G4 is not possible.

    I found that assignment was enjoyable even though it took time to find out that G 4 was not possible. However, I understood that the purpose of it was to enhance our critical thinking. Since the most important part of this course is about proof, which involves critical thinking. Therefore, this assignment starts preparing us for the upcoming lesson.

  15. Christopher Cruz
    Had troubles posting this from my computer.

  16. Matthew Schwartz

    I am having trouble articulating my path but I created videos of myself solving g1,g2,g3, g4 *I* cannot solve

    • Matthew Schwartz

      part 4
      I enjoyed this because I learned that I have some sort of mental disconnect between my ability to solve this sort of problem and my ability to articulate the solution. I think graphs are absolutely beautiful and look forward to learning more about them. This is very connected to what we are learning in class because math is all about relationships of objects and sets, and graphs are one way to express relationships- and Stephen Wolfram would argue the best way to order the relationships of the laws of the universe.

Leave a Reply

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