Suppose that a courier is delivering parcels in a neighborho

Suppose that a courier is delivering parcels in a neighborhood, depicted below as a graph where the edges represent segments of streets and the vertices intersections. If she starts in the top left corner and has to traverse every segment of every street, can she do so without retracing her steps? If not, what is the minimum number of streets segments that she would need to revisit? In either case, find a best possible tour.

Solution

for better understanding i am taking the numbering of these dots which starts from top left

1--2--3--4

5--6--7--8

9--10--11--12

so from this there is a connection between 2 and 5 .

so while delivering parcels in a neighbourhood. if she starts in the top left corner and has to traverse every

segment of every street without retracing her steps.

she starts from numbering 1 and then towards 2 then 6 ---- 7 ----3---4---8---12----11---10---9---5

clearly there is no step retraced from the above mentioned way

i.e., 1---2---6 ---- 7 ----3---4---8---12----11---10---9---5

Hence, this is the best possible tour to deliver parcels.