Conformance testing using test sequences is used to ensure that a protocol implementation conforms to its specification. A commonly used technique to generate test sequences for specifications described by the finite state machines is the Wp-method with the Reset technique, which frequently results in long test sequences. In this paper, we propose a bipartite graph approach to generate optimal test sequences for protocol conformance testing. Our approach significantly reduces the length of the test sequences required for conformance testing while maintaining the same fault detection capability.