2
$\begingroup$

Reading the book "Introduction to Graph Theory" (West, 2nd ed.) I have come across the following definition and statement:

enter image description here

Why is this statement true ?

Suppose I have a graph $G$ that consist of a cycle $C$ and a path $P$ that share no vertices. Then $G$ has an ear decomposition ? Well, I can decompose $G$ into $P_o = C$ and $P_1 = P$ ? $P_o$ is a cycle and $P$ is an ear of $P_0 \cup P_1$ - $P$ is a maximal path whose interval vertices have degree $2$ in $G$ ? But $G$ is not connected and therefore is $0$-connected and not $2$-connected ?

enter image description here

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Which book Introduction to Graph Theory? Amazon UK lists at least five books with that exact title (Chartrand and Zhang, Trudeau, Voloshin, West, Wilson). $\endgroup$ – David Richerby Feb 15 '14 at 22:05
  • 1
    $\begingroup$ From the image I think it's the one by West. $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 16 '14 at 0:03
  • $\begingroup$ The one by West 2nd edition $\endgroup$ – Shuzheng Feb 16 '14 at 7:03
6
$\begingroup$

"Ear decomposition" is not a term I've heard before but it's incorrectly defined, as you've observed, since it doesn't require that the graph be connected, let-alone 2-connected. An "ear" needs to be defined as having each endpoint adjacent to at least one further vertex of $G$. (Actually, each endpoint would have to be adjacent to at least two further vertices, or the path wouldn't be maximal.)

With the correct definition, the theorem is true.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Are you sure about this ? I mean the book is in 2nd edition and has probably been revised by many. A wrong definition and characterization would have been pointed out before printing ? (especially in 2nd edition) ? $\endgroup$ – Shuzheng Feb 16 '14 at 9:35
  • 1
    $\begingroup$ Yes, I'm sure: your counterexample is simple and clearly meets the definitions given in the image. I agree that it's surprising to see such an elementary mistake in a book, especially if the mistake was in the first edition, too. But, for example, see Diestel's book Graph Theory (online version): Whitney's theorem is Proposition 3.1.1; the definition of $H$-path (equivalent to an "ear") is at the bottom of page 7 in Section 1.3. The theorem is the same; the definition requires $H$-paths to meet the rest of the graph at both ends. $\endgroup$ – David Richerby Feb 16 '14 at 9:44
  • $\begingroup$ Thank you David for clearing this out and for you reference online book. $\endgroup$ – Shuzheng Feb 16 '14 at 9:51
  • 2
    $\begingroup$ You're welcome. You should contact the author or publisher and let them know of the mistake: maybe it'll be corrected for the third edition! $\endgroup$ – David Richerby Feb 16 '14 at 9:53
  • $\begingroup$ There is a wikipedia article on ear decompositions that seems to make the same oversight as Wests' book (defining ear decompositions without requiring connectivity): en.wikipedia.org/wiki/Ear_decomposition $\endgroup$ – JimN Feb 19 '14 at 19:16

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.