# 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

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.
• @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