In many application areas, it is necessary to specify and check properties of graphs. Such properties may be complex, placing structural requirements on graph regions of unbounded size. In this paper, we show that alternating graph automata can check such graph properties, e.g., whether a given input graph is a tree, or whether it contains a Hamiltonian cycle or not. In fact, we show that these automata can accept PSPACE-complete graph languages, and that their uniform membership problem is contained in PSPACE when only automata without permutation cycles are considered.