On graphs and valuations