How does columbo deduce the plot ?

The little things didn't sit well with him, and he used common sense, experience (100 cases a year) and intuition to piece it together.

I think the very first clue was when the phone rang the second the Dr got home from his trip. Columbo heard the plan to make the meeting at his office the next day. He tells himself, hmmm, the caller knows exactly when he is getting home from his trip and he has not talked to anyone while he was away or else he would have heard about the newspaper articles about his wife's death. So he say, "I'm going to make that appointment, too, and if that caller is an attractive woman, I will be suspicious." sure enough its a young girl who sort of looks like his wife.

His biggest clue is observing Dr. Fleming walking into the apartment after he returns from Mexico.

The not-so-good Doctor sees a tape outline on the carpet and doesn't react. He doesn't call for his wife. He doesn't go for a closer look. Nothing. Like he was expecting it. That's a HUGE red flag to Columbo, waiting in the next room. Then as mentioned above, the phone call, almost immediately after his return. Like she knew what time he'd be arriving home. The timing was quite suspicious.

Then after talking to the airline witnesses, revealing how "Mrs. Fleming" was hiding and covered up, Columbo figured out the ruse. Husbands are always the #1 suspect when wives get whacked.