和 and 跟 mean exactly the same thing 'with'. My understanding is, it's personal preference which you use. And, like so many things in Chinese, people from different regions prefer different words. I tend to use 跟 mostly. A native speaker may disagree though, so don't take my word for it.

in those three sentences you can use both 和 and 跟. 和。。。有//没有关系 and 跟。。。有//没有关系 are the same to me. at least in my 24 years of Chinese speaking life, I never met a situation where i should use them differently.

"和。。。有//没有关系 "and" 跟。。。有//没有关系"actually the same meaing.Both can be used in spoken English. "和。。。有//没有关系" is more in written language. " 跟。。。有//没有关系" is more in spoken language.

They have the same meaning in spoken language. But “和” is more desirable in writing.