We consider incomplete trace-based network proof systems for safety properties, identifying extensions that are necessary and sufficient to achieve relative completeness. We then consider the expressiveness required of any trace logic that encodes these extensions.