Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If a graph G is H-decomposable does it imply that G has H-factor?

share|cite|improve this question

No. An $H$-factor is a set of vertex-disjoint copies of $H$ that partition the vertex set of a graph, while an $H$-decomposition is a set of edge-disjoint copies of $H$ that partition the edge set of a graph.

For example, let $H = K_3$ and let $G$ be the $5$-vertex graph consisting of two triangles with a point in common. Then $G$ clearly has an $H$-decomposition, but, since $3 \nmid 5$, it cannot have an $H$-factor.

share|cite|improve this answer
Say i have a graph G with 3m vertices, and that G is $C_3$-decomposable. Can i say now that G has $C_3_-factor? – kim_kibun Feb 21 '13 at 14:44
@kim_kibun Again, not necessarily. Let $G$ be the $6$-vertex graph obtained by taking a triangle and adding three vertices, each adjacent to two of the vertices of the triangle. (More formally, let the vertices of the triangle be $u$, $v$, and $w$, and let the other three vertices be $a$, $b$, and $c$. Let $a$ be adjacent to $u$ and $v$, $b$ to $v$ and $w$, and $c$ to $w$ and $u$.) Then $G$ has a $K_3$-decomposition but no $K_3$-factor. – Andrew Uzzell Feb 21 '13 at 18:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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