Compact representation of paths in a graph
A Trie might do the trick: http://en.wikipedia.org/wiki/Trie

Label each edge of your graph with a letter.  Then add the strings which represent paths through your graph to the trie.  To fulfill the requirement that "no other paths apart from the selected ones are represented" you could leave all vertices of the trie blank, and label the edges, except when the edges leading from the root to the vertex represent one of your paths, then label the vertex with something.  A bool, the number of the path under some ordering, etc. 

Once you have your trie built, there are algorithms for compressing it down to an optimal (or near optimal) representation.  (see the linked Wikipedia article.)