-4
$\begingroup$

Suppose $G, H$ are finite, simple, undirected graphs and there is a bijection between the vertex sets $\varphi:V(G) \to V(H)$ such that for all $v\in V$ we have $$\text{deg}_G(v) = \deg_H(\varphi(v)).$$

Does this imply that $G\cong H$? In case the answer is positive, does it remain so if we consider infinite graphs?

Improve this question
$\endgroup$
1
  • 7
    $\begingroup$ Of course not. Otherwise, all $k$-regular graphs with the same number of vertices would be isomorphic. $K_{3,3}$ and the triangular prism is a concrete counterexample. $\endgroup$
    – Tony Huynh
    Jan 9, 2016 at 18:04

2 Answers 2

Reset to default
3
$\begingroup$

No, consider the Petersen graph and another with no star in the middle but just a simple pentagon. The former has no 4-cycle, but the latter has one.

Improve this answer
$\endgroup$
2
  • 9
    $\begingroup$ There is a saying: Never conjecture anything in graph theory before trying the Petersen graph! :) $\endgroup$
    – Wolfgang
    Jan 9, 2016 at 17:46
  • $\begingroup$ Excellent one! Will keep it in mind. $\endgroup$
    – Dominic van der Zypen
    Jan 9, 2016 at 19:28
4
$\begingroup$

If the answer were yes for finite graphs, the Graph Isomorphism computational problem would be trivially in $P$. This is not known. In fact, Babai recently showed with quite a bit of effort that it is in pseudo-polynomial time, and this was a major breakthrough.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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