Is SerializedSubject necessary for thread-safety in RxJava

Do I have to call toSerialized() on such Subject assuming I don't care if "A" goes before or after "B"?

Yep use toSerialized() because all operators applied to the subject assume that proper serialization is occurring upstream. The stream may fail or produce unexpected results if this does not happen.

Is Subject thread-safe anyway or will I break RxJava without toSerialized()?

answered above

What is the "Observable contract" that the documentation mentions?

Rx Design Guidelines.pdf section 4 defines the Observable contract:

4.2. Assume observer instances are called in a serialized fashion

As Rx uses a push model and .NET supports multithreading, it is possible for different messages to arrive different execution contexts at the same time. If consumers of observable sequences would have to deal with this in every place, their code would need to perform a lot of housekeeping to avoid common concurrency problems. Code written in this fashion would be harder to maintain and potentially suffer from performance issues.

I think RxJava documentation should make this more discoverable so I'll raise an issue.

According to Dave's answer, if you know beforehand that your Subject is going to be accessed from different threads, you could wrap it into a SerializedSubject http://reactivex.io/RxJava/javadoc/rx/subjects/SerializedSubject.html

Wraps a Subject so that it is safe to call its various on methods from different threads.

like: private final Subject<Object, Object> bus = new SerializedSubject<Object, Object>(PublishSubject.create());

(taken from Ben Christensen's EventBus example here: http://bl.ocks.org/benjchristensen/04eef9ca0851f3a5d7bf )