Definition of an abstract, combinatorial graph

Question

I have $0$ background in graph theory. I was recently reading an overview/history article of loop quantum gravity here: And in Appendix A, we state that, among other things, a basis state in the Hilbert space for LQG is characterized by a (abstract, combinatorial graph). I am looking for a precise mathematical definition of these terms (tried googling around but couldn't find anything concrete), or if I need a lot of background to understand it, maybe a text recommendation at an introductory level.

Answer 1

I think you may relax, because, as far as I know, by an abstract, combinatorial graph is understood a usual graph. The words abstract and combinatorial belong not to a formal mathematical definition, but remark that we consider a graph as a set of vertices and edges, and we are not tied to its concrete realization, for instance, to a drawing on a plane.

Answer 2

An abstract, combinatorial graph may just be a usual graph as Alex noted.

Still, in some contexts, the notion of abstract graph has a precise definition. Just as with other structures (groups, monoids, vector spaces...) what is interesting with graphs has to do with the associated notion of morphism. Then, a concrete graph is just a normal graph and an abstract graph is a usual graph up-to isomorphism, usually defined as the equivalence class of a concrete graph.

The distinction is not always made. It is important in algebraic treatment of graphs (see the beginning of the second chapter of "Graph structure and monadic second-order logic: a language-theoretic approach" by Courcelle and Engelfriet for example).

I do believe that at some point abstract replaced combinatorial. For example the article "characterization and recognition of partial 3-trees" by Arnborg and Proskurowski. They use "combinatorial graphs" without definition, but in proofs they use the fact that their graphs are defined up-to isomorphism.