Graphs of the form K1n are called stars Prove that if Krs is

Graphs of the form K_1,n are called stars. Prove that if K_r,s is a tree, then it
must be a star.

Solution

Suppose that r,s>1. Let x₁ and x₃ be in one partite sets, and x₂ and x₄ be in the other. Then

x_1,x₃,x₂,x₄

is a cycle. So if K_r,s is to have no cycle, it must be true that either r or s is one.