Multiple Choice

A graph is encoded as a string by listing the number of vertices, followed by a semicolon, followed by a list of

the edges

in the graph. The graph encoding is used to define a language L$.$

A string is in the language $L$ if and only if the string is a valid encoding of a graph and the graph contains a pa

th in which

every vertex appears exactly once.

Select the string that is in the language.

$5$;$(3,4),(4,2),(2,1),(1,3),(2,2),(3,1)$

$(3,4),(4,1),(4,2),(2,4),(1,2)$

$4$;$(3,3),(4,3),(2,1),(1,3),(2,2),(3,1)$

$4$;$(3,4),(4,2),(2,1),(1,3),(2,2),(3,1)$