0
$\begingroup$

Determine a decomposition of the Grötzsch graph into 3 paths. Enumerate these paths by their vertices.

I see why there must be 3 about the center vertex (w by convention in the Mycielskian), but what is the specific enumeration here. The other stack exchange question on this topic provides an enumeration with 19 edges, which cannot be correct. How should i find this decomposition?

$\endgroup$
0
$\begingroup$

There are six vertices of odd degree: one of degree 5 and five of degree 3. Pick four of the degree 3 vertices and connect them in pairs by two edge pasths across the degree 5 vertex. Then find an Euler path for the rest by starting at one of the two remaining odd vertices and ending at the other

enter image description here

$\endgroup$
  • $\begingroup$ This has the core idea about the vertex w (by convention in the labeling of the mycielskian), but I would be looking for the actual enumeration to be present in the answer. I have since found it, but if you add the enumeration, I will accept your answer. $\endgroup$ – rjm27trekkie Sep 17 '18 at 13:32

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.