Can we represent all computer programs as graphs?
I don't know if it's a particularly well known equivalence, but it's fairly simple when you think about it.

Turing Machines are known to be equivalent to the (untyped) Lambda Calculus. The Church-Turing thesis proposes that this is they are the most powerful form of computation.

The Lambda Calculus is a syntactically defined term re-writing system. Essentially, it's a very simple programming language. So, it can be parsed into an abstract syntax tree (graph).

So, we have:


Every computer program is representable in the untyped lambda calculus.
Every lambda calculus program can be parsed into an abstract syntax tree


This means that every computer program can be represented as a Lambda Calculus abstract syntax tree.

These trees might not have much in the way of interesting properties. For example, they're definitely not unique i.e. two different trees can perform identical computations.