1
$\begingroup$

Imagine that you have 2x conncected graphs and they have the same number of vertrices of each degree and the same number of cycles of each length how does it come up despite these facts that they are not isomorphic?

Aren't these facts obvious if they have the same number of vertrices and the same degree and the same length of cycle i don't understand how to find a counterexample?

$\endgroup$
1
  • $\begingroup$ It's not clear how many nonisomorphic connected graphs you want; you wrote $2x$ but what is $x$? $\endgroup$
    – user14111
    Feb 20 at 6:42

1 Answer 1

2
$\begingroup$

Hint: look for two non-isomorphic connected graphs without any cycles (trees), each of which has one vertex of degree 3, two vertices of degree 2, and three vertices of degree 1.

Alternative hint: take a connected graph, add an isolated vertex, and see how many different ways you can add an edge from the isolated vertex to one of the vertices of the graph—maybe two different ways still lead to the same degree counts.

$\endgroup$

You must log in to answer this question.

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