I am adding "undo" functionality to a small Android app that lets you edit some graph. Should I put this on the "back" button? Or somewhere else? What is the best place for this?
You shouldn't do that.
Android users will expect the button to navigate back. If you want an undo, add an action to the action bar or provide it via a popup (http://developer.android.com/design/patterns/confirming-acknowledging.html)
No, it is not ok.
From the Android Developer Guidelines, Providing Proper Back Navigation:
Back navigation is how users move backward through the history of screens they previously visited. All Android devices provide a Back button for this type of navigation, so your app should not add a Back button to the UI.
Android has a clear use pattern for the Back button, which is allowing the user to move back in screen history. Changing this will only serve to confuse users.
The first sentence in the Android Design Guidelines for Navigation with Back and Up points exactly to this point:
Consistent navigation is an essential component of the overall user experience. Few things frustrate users more than basic navigation that behaves in inconsistent and unexpected ways.
You should maintain the expected functionality of the Back button, as documented in the link above, to provide a consistent navigation pattern within your app. Doing otherwise will not benefit your users.