  We study entanglement properties of mixed density matrices obtained from
combinatorial Laplacians. This is done by introducing the notion of the density
matrix of a graph. We characterize the graphs with pure density matrices and
show that the density matrix of a graph can be always written as a uniform
mixture of pure density matrices of graphs. We consider the von Neumann entropy
of these matrices and we characterize the graphs for which the minimum and
maximum values are attained. We then discuss the problem of separability by
pointing out that separability of density matrices of graphs does not always
depend on the labelling of the vertices. We consider graphs with a tensor
product structure and simple cases for which combinatorial properties are
linked to the entanglement of the state. We calculate the concurrence of all
graph on four vertices representing entangled states. It turns out that for
some of these graphs the value of the concurrence is exactly fractional.
