Enterprises often have no integrated and comprehensive view of their enterprise topology describing their entire IT infrastructure, software, on-premise and off-premise services, processes, and their interrelations. Especially due to acquisitions, mergers, reorganizations, and outsourcing there is no clear ‘big picture’ of the enterprise topology. Through this lack, management of applications becomes harder and duplication of components and information systems increases. Furthermore, the lack of insight makes changes in the enterprise topology like consolidation, migration, or outsourcing more complex and error prone which leads to high operational cost. In this paper we propose Enterprise Topology Graphs (ETG) as formal model to describe an enterprise topology. Based on established graph theory ETG bring formalization and provability to the cloud. They enable the application of proven graph algorithms to solve enterprise topology research problems in general and cloud research problems in particular. For example, we present a search algorithm which locates segments in large and possibly distributed enterprise topologies using structural queries. To illustrate the power of the ETG approach we show how it can be applied for IT consolidation to reduce operational costs, increase flexibility by simplifying changes in the enterprise topology, and improve the environmental impact of the enterprise IT.