def is_walk(g, walk):
  """
  Given a graph 'g' and a list 'walk', return true
  if 'walk' is a walk in g.

  Recall a walk in a graph is a nonempty
  sequence of vertices
  in the graph so that consecutive vertices in the
  sequence are connected by a directed edge
  (in the correct direction)

  Efficiency: O((# edges) * (walk length))

  >>> Edges = [(1,2),(1,3),(2,5),(3,4),(4,2),(5,4)]
  >>> g = Graph({1,2,3,4,5}, Edges)
  >>> is_walk(g, [3,4,2,5,4,2])
  True
  >>> is_walk(g, [5,4,2,1,3])
  False
  >>> is_walk(g, [2])
  True
  >>> is_walk(g, [])
  False
  >>> is_walk(g, [1,6])
  False
  >>> is_walk(g, [6])
  False
  """

  if not walk: # should have at least one vertex
    return False

  if len(walk) == 1:
    return g.is_vertex(walk[0])

  # num iterations = O(len(walk))
  for i in range(len(walk)-1):
    # body of loop takes O(# edges) time, can improve with a different
    # implementation of the Graph() class method, but we don't need to
    # for 275
    if not g.is_edge((walk[i], walk[i+1])):
      return False

  return True