Prove the following:
- If G≅H then G and H have the same maximum degree.
- If G≅H then G and H have the same number of vertices of maximum degree.
- If G≅H then there is an isomorphism of induced graphs on the vertices of maximum degree.
How do I prove (1) and (2) without just simply saying there exists a bijection between the two and by the definition of isomorphism and bijection, they are one-to-one? I don't know what the professor is looking for here as far as a proof goes. Would a contradiction of some sort be sufficient?
For (1) and (2), show that if $\phi:G\to H$ is an isomorphism, then $v$ and $\phi(v)$ have the same degree for all $v\in V(G)$. Because $\phi$ must be a bijection on the vertex set, this implies that $G$ and $H$ have the same degree sequences.