Both waxy potatoes and all-purpose potatoes can be boiled either whole or cut, while starchy potatoes should only be boiled whole to minimize the amount of water they absorb. To cook any type of potato, place them in a pot, add enough cold water to cover them by an inch, sprinkle a generous pinch of salt, and turn the heat to high.