I would like to find the graph underlying the map. The nodes are the intersections and the edges are the sidewalks. I can use graph theory algorithms to find the shortest path.

There is a similar question here referring to Google Maps.

I would like to apply Fleury’s algorithm, Dijkstra’s algorithm, and A* to answer questions about going for a walk around the neigborhood.

Is there a way to extract a graph object from the map using the Open Street Map API?

There are actually lots and lots of ways. There is a whole host of routing software for OSM, allowing use a broader range of algorithms than you list. Plenty of these offer out-of-the-box routing for cars, but pedestrian profiles may need a bit of coding.