We consider a three-node half-duplex Gaussian relay network where two nodes (say a, b) want to communicate with each other and the third node acts as a relay for this two-way communication. Outer bounds and achievable rate regions for the possible rate pairs (Ra, Rb) for two-way communication are investigated. The modes (transmit or receive) of the half-duplex nodes together specify the state of the network. A relaying protocol uses a specific sequence of states and a coding scheme for each state. In this paper, we first obtain an outer bound for the rate region of all achievable (Ra, Rb) based on the half-duplex cut-set bound. This outer bound can be numerically computed by solving a linear program. It is proved that at any point on the boundary of the outer bound only four of the six states of the network are used. We then compare it with achievable rate regions of various known protocols. We consider two kinds of protocols: (1) protocols in which all messages transmitted in a state are decoded with the received signal in the same state, and (2) protocols where information received in one state can also be stored and used as side information to decode messages in future states. Various conclusions are drawn on the importance of using all states, use of side information, and the choice of processing at the relay. Then, two analytical outer bounds (as opposed to an optimization problem formulation) are derived. Using an analytical outer bound, we obtain the symmetric capacity within 0.5 bits for some channel conditions where the direct link between nodes a and b is weak. © 2012 IEEE.