Do two waves with same frequency, automatically have same wavelength? If you have two waves which have the same frequency, is it implied then that they have to have same wavelength? Will there be a scenario when two waves with same frequency have different wavelength?
 A: For example, in a birefrigent medium (https://en.wikipedia.org/wiki/Birefringence), the wavelength depends on the polarization, so two waves in the same medium and with the same frequency but different polarization can have different wavelengths. 
A: 
If you have two waves which have the same frequency, is it implied then that they have to have same wavelength

Nope nope nope. That's only when you're assuming that they're travelling through the same medium and have the same polarisation.
Here's a simple counter example: Humans identify light with a frequency of $\approx 450\ \rm THz$ as red light. That's the way our eyes work. We know that the frequency of light remains the same when it travels from one medium to another, so when I'm underwater, the wavelength of the red light I see is about $450\ \rm nm$, but when I'm in a vacuum, the wavelength is about $600\ \rm nm$. Same colour observed, same frequency, but different wavelengths.
A: If they have the same speed, then yes, they will.
frequency = cycles/time
wavelength = distance/cycle
So by simple algebra, speed = frequency * wavelength
If the waves have different speeds, they will differ in wavelength though.
A: I am an amateur that conducted an experiment on this very topic. Yes, there are situations where the frequency remains constant but the wavelength changes. This will affect the speed at which the wave travels. The wavelength contracts when it passes through a medium (note: I have not tested all mediums) Here’s a link to my experiment: Is the decrease in wavelength proportional to the reduction in speed?
The contraction appears to be proportional to the reduction in speed. The test was simply to place a diffraction grating above water and measure the separation. Then perform the same test under water and measure. There was an obvious reduction in wavelength, but the color seemed to remain the same. This indicated that the frequency remained constant. Once again, please note this was an amateur experiment done in my garage, but I think it holds water, pun intended.
