-1
$\begingroup$

The Tuza theorem states that every graph with no cycle congruent to 1 mod $k$ is $k$ colorable. Now, the line graph of any simple graph of maximum degree $d$ is seen to posess the property that it has no cycle of length congruent to $d+1$(as all cycles have lengths strictly less than $d+1$). So, I think this leads to another proof of the Vizing's theorem.

Is this right, or am i missing some subtle point? Thanks beforehand.

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ I'm voting to close this question because the comment and answer below indicate that not enough thought was put into the question before asking it $\endgroup$
    – Yemon Choi
    Commented Dec 19, 2019 at 20:04

1 Answer 1

Reset to default
0
$\begingroup$

I think the major error in the purported proof is that the line graph has all its cycles having length not congruent to 1 mod $d+1$ is non trivial(there are cycles having length greater than $d+1$), or is altogether false in some cases ( as shown by the example given by @bof below in the comment).

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ If $G$ is the $1$-skeleton of the dodecahedron, then $G$ is $3$-regular, and both $G$ and its line graph have cycles of length $5$. $\endgroup$
    – bof
    Commented Dec 10, 2019 at 11:29

You must log in to answer this question.

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