**The assignment below is due BEFORE CLASS on Thursday, October 11th (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 mathisfun.com 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/11 (beginning of class)

**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 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.

Example:

Here is a puzzle: http://sketchtoy.com/67467551

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

PART 4. 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 sketchtoy.com – it allows you to draw something, then click “SAVE” 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?): http://sketchtoy.com/67467556

G1) START AT: ED, DC, CB, BA, AI, IB, BH, HI, IC, CH, HG, GD, DF, FG, GE, EF

G2) START AT: CB, BA, AF, FC, CD, DE, EB, BF, FE

G3) START AT: ED, DC, CB, BA, AJ, JB, BI, IJ, JC, CI, IH, HD, DG, GH, HE, EF, FG, GE

G4) START AT: EF, FA, AB, BF, FC, CB, BE, ED, DA

file:///var/folders/33/7lkfp88d62b34zzgmt1khwsh0000gn/T/IMG_0195%202.jpg

The fact that no bridge could not be “walked over” twice is directly connected to what we did in class. I thought it was fun, and strangely addictive. Once you get started, you want to keep on trying. Very cool.

Part one

1) FG, GD, DF, FE, EG, GH, HB, BI, IC, CH,HI, IA, AB, BC, CD, DE

2) EF, FB, BE,ED,DC, CF, FA, AB, BC

3)GH, HD, DG, GE, EH, HI, IB, BJ, JC, CI, IJ, JA, AB, BC, CD, DE, EF, FG

4)I don’t think it is possible to get a solution for the fourth image. I’ve tried but my problem is i cant fit in the line segment through the middle.

Part3)http://sketchtoy.com/68770532

Part 4)

I Enjoyed this assignment a lot. The assignment felt like a game and I love games. I think this assignment is meant to show us that starting at a specific point is important. we need to choose where we start because it can affect the outcome. That relates to proving theorems i think? o.o

Junior, label the points of your puzzle!

http://sketchtoy.com/68770662

I forgot to put in vertices so I redid it. I did not label the vertices by letter but color instead because it seemed easier

http://sketchtoy.com/68770874

Solution to Danping Zhong’s puzzle. CA, AD, DB, BE, EC, CB, BA, AE, ED, DC

Part one

1) F->D->E->F->G->H->C->I->B->A->I->H->B->C->D->G->E.

2) E->D->C->B->A->F->E->B->F->C.

3)G->F->E->D->C->B->A->J->C->I->B->J->I->H->E->G->H->D->G.

4) The last puzzle has NO solution.

Part one

1) F->D->E->F->G->H->C->I->B->A->I->H->B->C->D->G->E.

2) E->D->C->B->A->F->E->B->F->C.

3)G->F->E->D->C->B->A->J->C->I->B->J->I->H->E->G->H->D->G.

4) The last puzzle has NO solution.

Part two

http://sketchtoy.com/68771881

http://sketchtoy.com/68771892

Part three

Concerning Dunping’s solution of https://sketchtoy.com/68770874

A->B->D->E->C->A->E->B->C->D->A

Part four

1. To sharpen our brains

2. To interact with peers

3. To love the subject even more

Part One

G2) CB,BA,AF,FE,EB,BF,FE,CD,DE

G4) There is no solution for G4

G1) EG,GD,DC,CB,BH,HI,IA,AB,BI,IC,CH,HG,GF,FE,ED,DF

PART 1.

1) E,F.D,E,G,D,C,H,B,C,I,B,A,I,H,G,F

2) C,F,E,D,C,B,A,F,B,E

3) E,G.D,E,H,D,C,I,B,C,J,B,A,J,I,H,G,F,E

4)I think there is no solution.

PART 2.

http://sketchtoy.com/68770874

http://sketchtoy.com/68770877

PART 3.

http://sketchtoy.com/68770662

Junior’s puzzle solution: red, purple, blue, yellow, green, orange, red, yellow, purple, orange, yellow

PART 4.

I enjoyed this assignment. Because this puzzle is challenged but also interesting. I had this game in my phone before, but I didn’t know the theory behind it. I think we can figure it out how many possible path by what we learned in class, and I believe there are some logic behind it.

Part 1:

G1: E,F,G,E,D,C,I,A,B,A,I,H,B,C,H,G,D,F

G2: C,D,E,F,A,B,C,F,B,E

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

G4: I couldn’t find a solution to this puzzle.

Part 2:

1. https://sketchtoy.com/68770750

2. https://sketchtoy.com/68770754

Part 3:

Here’s my solution to Junior’s puzzle: yellow, green, orange, red, yellow, orange, pink, yellow, blue, pink

Part 4:

I enjoyed this assignment because I’ve always loved solving puzzles. This assignment reminded me of completing a maze, which I loved doing as a kid. This exercise can be connected back to our discussion of lists, where order matters. To cross over all the bridges we had to make a list of all of the edges of the maps without repetition. Everyone’s list will surely be different, even though they contain the same elements.

Part 3:

2)Solution to Richel puzzle #2: J,A,BJ,I,B,C,I,H,,C,D,H,G,D,E,G,F,E

Is there any solution for your puzzle? I couldn’t find any.

part1

G1:E,F,G,E,D,C,I,A,B,A,I,H,B,C,H,G,D,F

G2:C,F,E,D,C,B,A,F,B,E

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

G4:I don’t think there is a solution for that one.

part2

1.https://sketchtoy.com/68771796

part3:

Here’s my solution to rachel’s puzzle #2:

J,I,H,G,F,E,D,C,B,AJ,B,I,C,H,D,G,E

Part4:

I did not enjoy this exercise because i failed to find the solutions of some of the puzzles. It is challenging to find a solution to one of this puzzles and the frustration that come when you think you finally find something which is not is killing me. I’m not saying that i want easy puzzle, i just don’t like not be able to complete that problem.

PART 1.

G1) E, G, D, C, B, A, I, B, H, I, C, H, G, F, D, E, F

G2) E, B, F, C, D, E, F, A, B, C

G3) I, J, A, B, J, C, B, I, C, D, E, F, G, E, H, D, G, H, I

G4) I worked extra hard to figure out to solve this puzzle, but I couldn’t find any solution. I think this puzzle has no answer.

PART2.

1)https://sketchtoy.com/68771851

2)https://sketchtoy.com/68771859

PART3.

Here’s my solution to Danping’s puzzles #1 and 2:

1) C, A, D, B, E, C, B, A, E, D, C

2) C, A, E, C, B, D, F, B, A, F, E, D, C

PART4.

Yes! I definitely enjoyed this assignment because solving a puzzle makes me relaxed and helps me to get rid of negative and stressful thoughts. When solving a puzzle, we try to make a picture come together, but we work extra hard to figure out where those pieces go. I think this assignment gave us an idea of how to figure out how to solve a puzzle without a picture and it would help us to figure out how to write a proof and understand the “list of functions and symbols.”

PART 2:

1) Solution to Jesstopal puzzle #1: D,F,C,E,B,D,E,A,C,D

Part one

1) F->D->E->F->G->H->C->I->B->A->I->H->B->C->D->G->E.

2) E->D->C->B->A->F->E->B->F->C.

3)G->F->E->D->C->B->A->J->C->I->B->J->I->H->E->G->H->D->G.

4) The last puzzle has NO solution.

Part two

http://sketchtoy.com/68771881

http://sketchtoy.com/68771892

Part three

Concerning Dunping’s solution of https://sketchtoy.com/68770874

A->B->D->E->C->A->E->B->C->D->A

Part four

1. To sharpen our brains

2. To interact with peers

3. To love the subject even more

Part 1:

G1: Start: F, E,G,D,C,H,B,I,A,B

G2: Start: F,A,B,E,D,C,F

G3: Start: G,F,E,H,D,C,I,B,J,A,B

G4: Start: A,D,E,B,F,C

Part 2:

http://sketchtoy.com/68772158

http://sketchtoy.com/68772161

Part 3:

My solution to Danping http://sketchtoy.com/68770874

Start: B,A,C,E,D,B,E

Part 4:

I enjoy the exercise, I feel the the puzzles where a little challenging. This app I have on my phone called Peak – Brain Training, they have puzzle just like this on there and other games. There are many different ways to have solutions to the puzzles which makes it more interesting.

PART3.

Here’s my solution to Danping’s puzzles #1 and 2:

1)http://sketchtoy.com/68770874

C, A, D, B, E, C, B, A, E, D, C

2) http://sketchtoy.com/68770877

C, A, E, C, B, D, F, B, A, F, E, D, C

PART2.

1) https://sketchtoy.com/68771851

2) https://sketchtoy.com/68771859

Part 1

G1 E,F.D,E,G,D,C,H,B,C,I,B,A,I,H,G,F

G2 C,F,E,D,C,B,A,F,B,E

G3 E,G.D,E,H,D,C,I,B,C,J,B,A,J,I,H,G,F,E

G4 no solution

Part 2

http://sketchtoy.com/68772198

http://sketchtoy.com/68772199

Part 3

Danping solution: A,C,E,B,D,E,A,B,C,D

Part 4

I somewhat enjoyed the assignment because I am not into puzzles. I imagine this is connected to class work because we are doing proofs which follows a certain path.

Part #1

G1) ED, DC, CB, BA, AI, IB, BH, HI, IC, CH, HG, GD, DF, FG, GE, EF

G2) CF, FE, ED, DC, CB, BA, AF, FB, BE

G3) GF, FE, ED, DC, CB, BA, AJ, JC, CI, IB, BJ, JI, IH, HE, EG, GH, HD, DG

G4) No Solution

Part #2

http://sketchtoy.com/68772191

http://sketchtoy.com/68772196

Part #3

Solution to Yvan puzzle

BF, FE, EA, AB, BC, CD, DE, EC

Part #4

I enjoyed this assignment because it felt more like a game than an assignment. It was fun finding different ways of connecting the points. By not being allowed to cross a bridge twice, it makes it more challenging. It is important to choose a correct point to begin with for the puzzle to work out. This game can relate to what we talked about it class.

can anyone see my post?

Now we can!

G4. No solution. lol