Original: In 1868 another part of the western Utah Territory, whose population was seeking to avoid Mormon dominance, was added to Nevada in the eastern part of the state, setting the current eastern boundary.
Simplified: The eastern part of Nevada was part of "Utah Territory"  and the southern part was part of "New Mexico".