Nowadays, Web Services (WS) remain a main actor in the implementation of distributed applications. They represent a new promising paradigm for the development, deployment and integration of Internet applications. These services are in most cases unable to provide the required functionality; they must be composed to provide appropriate services, richer and more interesting for other applications as well as for human users. The composition of Web services is considered as a strong point, which allows answering complex queries by combining the functionality of multiple services within a same composition. In this work we showed how the formalism of graphs can be used to improve the composition of web services and make it automatic. We have proposed the rewriting logic and its language Maude as a support for a graph-based approach to automatic composition of web services. The proposed model has made possible the exploration of different composition schemas as well as the formal analysis of service compositions. The paper introduces a case study showing how to apply our formalization.