1
$\begingroup$

I need to construct 2 graphs that are non isomorphic and have 3 of the following properties.

  • Same number of vertices
  • Same number of edges
  • Both contain a closed eulerian path

I was thinking of the graph invariant to be "coherent components". With 1 graph containing 1 coherent component and the other one 2. But I couldn't get the number of edges the same.

Here's what I've tried:

2 Graphs

Does anyone know any examples of such graphs with these 3 properties, the invariant can also be something else.

Best regards

$\endgroup$
1
$\begingroup$

Each graph here has $6$ vertices, $8$ edges, and an Eulerian circuit. Each also has two vertices of degree $4$, but on the left, the two aren't adjacent, and on the right, they are, hence these graphs are nonisomorphic. I'm not sure what your observation about components was, but these two are connected, so it seems that that idea won't apply here.

enter image description here

EDIT: Some more examples for graphs on $8$ vertices, $10$ edges. It's also worth noting that the last example has a different degree sequence from the others. enter image description here

$\endgroup$
1
$\begingroup$

I recommend Kevin Long's answer, but the situation you might be trying to achieve would need to have edges in only one component to allow an Eulerian cycle - the other components would need to be isolated vertices. If in one case we have a cycle graph and in the other we have some other Eulerian graph, we could end up with something like this:

enter image description here

$\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.