Where's the graph theory in graphical models? Introductions to graphical models describe them as "... a marriage between graph theory and probability theory."
I get the probability theory part but I have trouble understanding where exactly graph theory fits in.  What insights from graph theory have helped deepen our understanding of probability distributions and decision making under uncertainty?
I am looking for concrete examples, beyond the obvious use of graph theoretic terminology in PGMs, such as classifying a PGM as a "tree" or "bipartite" or "undirected", etc.
 A: In a strict sense, graph theory seems loosely connected to PGMs. However, graph algorithms come in handy. PGMs started with message-passing inference, which is a subset of general class of message-passing algorithms on graphs (may be, that is the reason for the word “graphical” in them). Graph-cut algorithms are widely used for Markov random field inference in computer vision; they are based on the results akin to Ford–Fulkerson theorem (max flow equals min cut); most popular algorithms are probably Boykov–Kolmogorov and IBFS.
References. [Murphy, 2012, §22.6.3] covers graph cuts usage for MAP inference. See also [Kolmogorom and Zabih, 2004; Boykov et al., PAMI 2001], which cover optimization rather than modelling.
A: There has been some work investigating the link between the ease of decoding of Low Density Parity Check codes (which gets excellent results when you consider it a probablistic graph and apply Loopy Belief Propagation), and the girth of the graph formed by the parity check matrix. This link to girth goes right the way back to when LDPCs were invented[1] but there's been further work in the last decade or so[2][3] after the were separately rediscovery by Mackay et al [4] and their properties noticed.
I often see pearl's comment on the convergence time of belief propagation depending on the diameter of the graph being cited. But I don't know of any work looking at graph diameters in non-tree graphs and what effect that has.


*

*R. G. Gallager. Low Density Parity Check Codes. M.I.T. Press, 1963

*I.E. Bocharova, F. Hug, R. Johannesson, B.D. Kudryashov, and R.V. Satyukov. New low-density parity-check codes with large girth based on hypergraphs. In Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on, pages 819 –823, 2010.

*S.C. Tatikonda. Convergence of the sum-product algorithm. In Information Theory Workshop, 2003. Proceedings. 2003 IEEE, pages 222 – 225, 2003

*David J. C. MacKay and R. M. Neal. Near Shannon limit performance of low density parity check codes. Electronics Letters, 33(6):457–458, 1997.

A: There is very little true mathematical graph theory in probabilistic graphical models, where by true mathematical graph theory I mean proofs about cliques, vertex orders, max-flow min-cut theorems, and so on.  Even something as fundamental as Euler's Theorem and Handshaking Lemma are not used, though I suppose one might invoke them to check some property of computer code used to update probabilistic estimates.  Moreover, probabilist graphical models rarely use more than a subset of the classes of graphs, such as multi-graphs.  Theorems about flows in graphs are not used in probabilistic graphical models.
If student A were an expert in probability but knew nothing about graph theory, and student B were an expert in graph theory but knew nothing about probability, then A would certainly learn and understand probabilistic graphical models faster than would B.
A: One successful application of graph algorithms to probabilistic graphical models is the Chow-Liu algorithm. It solves the problem of finding the optimum (tree) graph structure and is based on maximum spanning trees (MST) algorithm.
A joint probability over a tree graphical model can be written as:
\begin{equation}
    p(x|T) = \prod_{t\in V} p(x_t) \prod_{(s,t) \in E} \frac{p(x_s, x_t)}{p(x_s)p(x_t)}
\end{equation}
We can write down a normalized log-likelihood as follows:
\begin{equation}
\frac{1}{N}\log P(D|\theta, T) = \sum_{t\in V}\sum_k p_{ML}(x_t=k) \log p_{ML}(x_t=k) + \sum_{(s,t)\in E} I(x_s; x_t|\theta_{st})
\end{equation}
where $I(x_s;x_t|\theta_{st})$ is the mutual information between $x_s$ and $x_t$ given the empirical Maximum Likelihood (ML) distribution which counts the number of times a node $x$ was in state $k$. Since the first term is independent of the topology $T$, we can ignore it and focus on maximizing the second term. 
The log-likelihood is maximized by computing the maximum weight spanning tree, where the edge weights are the pairwise mutual information terms $I(x_s;x_t|\theta_{st})$. The maximum weight spanning tree can be found using Prim's algorithm and Kruskal's algorithm.
