Если в графах поровну рёбер и вершин, то такие графы не всегда одинаковые.

Верно. Графы с одинаковым количеством ребер и вершин могут иметь разную структуру и, следовательно, быть разными. Например, один граф может быть связным, а другой - нет.