1
$\begingroup$

This is an elementary question, but I have been stuck for a while since I have not been able to prove or disprove this statement: If there exists a bijection f : V (G) → V (H) such that every vertex u ∈ V (G) has the same degree as f(u), then G and H are isomorphic.

But I don't know how to apply this definition:

"Two graphs G = (V,E) and G = (V , E ) are called isomorphic if a bijection f : V → V exists such that {x, y} ∈ E if and only if {f(x), f(y)} ∈ E holds for all x, y ∈ V , x = y. Such an f is called an isomorphism of the graphs G and G . The fact that G and G are isomorphic is written G ∼= G ."

to show that G and H are isomorphic since I have not been able to find a way to show that if {x, y} ∈ E(G), then {f(x), f(y)} ∈ E(H) since the question doesn't give any explicit information about the edges other than the fact that the two graphs have to have the same number (since the degree of each vertex and its image are the same).

My hunch is that the statement is true, but I cannot prove it. Any help would be thoroughly appreciated!

$\endgroup$
4
$\begingroup$

Your question is the same as asking if the degree sequence of a graph uniquely determines a graph, and that is false.

For example, consider the circle graph on six vertices versus a graph composed of two circle graphs on three vertices.

$\endgroup$
3
$\begingroup$

Isomorphisms preserve degree of vertices, but that condition is not sufficient. For a counterexample, let $G$ be $C_6$ (a cycle with $6$ vertices) and $H$ be the union of two copies of $C_3$. Then any bijection between the vertex sets of $G$ and $H$ preserves degree (since the degree of each vertex in either graph is $2$), but $G$ is connected while $H$ is not, so $\not\cong H$.

To see this directly from the definition, suppose $f$ is a bijection from $V(G)$ to $V(H)$. Let $u\in V(G)$ with neighbors $v$ and $w$. Then if $f(u)f(v), f(u)f(w)\in V(H)$, it follows that $f(v)f(w)\in V(H)$. But $vw\notin V(G)$, so $f$ is not an isomorphism.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.