# Is there a problem that cannot be represented using graph?

It is obvious that the representational power of graphs are huge.
Is there a problem that cannot be represented using graph?

I have recently asked this question to my students and no answers came up. I could not answer this either.

For instance:
Problem: Finding the shortest path between two given cities in a country.
Graph type: Directed, weighted.
Vertices: Cities.
Edges: An edge $(i,j)$ indicates there is a way from city $i$ to city $j$ and weight of $(i,j)$ indicates the distance between cities $i$ and $j$.

Problem: Expressing your feelings using crayons.
Graph type: Directed, weighted.
Vertices: Neurons in the brain.
Edges: Values of electronic signals being transmitted among neurons.
Output: Interpretation of the signals by the brain.
(Just kidding)

Edit: Problem in this post means, a problem that can be solved using computers.

• Define "scenario" and "represent". With loose definitions, the representational power of a sequence of !s is just as great. If you take !!! to be a number in unary, convert in to binary and interpret as a text file. – Karolis Juodelė May 26 '14 at 20:19
• "Express your feelings using crayons." – Raphael May 26 '14 at 21:20
• @Raphael please see my edit. – padawan May 26 '14 at 21:40
• What about "sum of three (or more) given numbers"? – mrmowji May 27 '14 at 1:03
• @Mowji Represent the natural number $i$ by any graph on $i$ vertices and sum by disjoint union. – David Richerby May 27 '14 at 7:50

## 1 Answer

It's trivial to encode natural numbers as graphs (represent $n$ by a path of length $n$, or by $K_n$) so anything that can be represented as numbers can be represented as graphs.

• No, that answer is too easy for me. Numbers have structure, mathematical context, they are not just counting. If you need numbers in a context a faithful representation should naturally represent that context. For example there should be a nice interpretation for "this number is prime". – Hendrik Jan May 27 '14 at 22:52
• @HendrikJan Peano got a long way by defining the natural numbers as the closure of $0$ under the successor operation: there's a lot you can do with "just counting". If you represent $n$ by $K_n$, then $n$ is prime iff it can't be written as a strong product except as $K_1\boxtimes K_n$. – David Richerby May 27 '14 at 23:40
• You are right on both these counts. Still I stress the comment by Karolis above: "represent" has to be defined and chosen in a natural way to fit the context. We can represent a Turing machine program by a labelled graph easily, but that doesn't make the halting problem into a graph problem. – Hendrik Jan May 27 '14 at 23:59