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.

  • 6
    $\begingroup$ 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. $\endgroup$ May 26, 2014 at 20:19
  • 1
    $\begingroup$ "Express your feelings using crayons." $\endgroup$
    – Raphael
    May 26, 2014 at 21:20
  • $\begingroup$ @Raphael please see my edit. $\endgroup$
    – padawan
    May 26, 2014 at 21:40
  • $\begingroup$ What about "sum of three (or more) given numbers"? $\endgroup$
    – mrmowji
    May 27, 2014 at 1:03
  • 1
    $\begingroup$ @Mowji Represent the natural number $i$ by any graph on $i$ vertices and sum by disjoint union. $\endgroup$ May 27, 2014 at 7:50

1 Answer 1


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.

  • $\begingroup$ 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". $\endgroup$ May 27, 2014 at 22:52
  • $\begingroup$ @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$. $\endgroup$ May 27, 2014 at 23:40
  • $\begingroup$ 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. $\endgroup$ May 27, 2014 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.