-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
    Commented 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
    Commented Jan 9, 2016 at 17:46
  • $\begingroup$ Excellent one! Will keep it in mind. $\endgroup$
    – Dominic van der Zypen
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .