European route E75 runs through the city and connects Heraklion with the three other major cities of Crete : Agios Nikolaos , Chania , and Rethymno .
The European route E75 runs through the city and connects Chania with the three other major cities of Heraklion : Agios Nikolaos , Crete and Rethymno .

Are these two sentences paraphrases of each other?
no