<p>"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&nbsp;$G$.  (Actually, each endpoint would have to be adjacent to at least two further vertices, or the path wouldn't be maximal.)</p>

<p>With the correct definition, the theorem is true.</p>

CC BY-SA 3.0
2014-02-16T09:35:36.273Z
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) ?
Shuzheng
CC BY-SA 3.0
2014-02-16T09:44:33.993Z
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](http://diestel-graph-theory.com/basic.html)): 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.
David Richerby
CC BY-SA 3.0
2014-02-16T09:51:42.840Z
Thank you David for clearing this out and for you reference online book.
Shuzheng
CC BY-SA 3.0
2014-02-16T09:53:27.870Z
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!
David Richerby
CC BY-SA 3.0
2014-02-19T19:16:31.780Z
There is a wikipedia article on ear decompositions that seems to make the same oversight as Wests' book (defining ear decompositions without requiring connectivity): http://en.wikipedia.org/wiki/Ear_decomposition
JimN
CC BY-SA 3.0
2014-02-23T14:06:31.637Z
@Jim The wikipedia article's OK. If you track through the definitions, an "open ear decomposition" builds up the graph from cycle and a bunch of paths. Each of the paths must have as its endpoints distinct vertices of the graph built up so far, and the internal vertices must be disjoint from the graph build up so far. Both endpoints being pre-existing vertices enforces connectivity (and, by the theorem, 2-connectivity).
David Richerby
CC BY-SA 3.0
2014-02-15T22:18:54.000Z
2014-02-15T22:32:35.743Z
2014-02-15T22:32:35.743Z
David Richerby
<p>Reading the book "Introduction to Graph Theory" (West, 2nd ed.) I have come across the following definition and statement:</p>

<p><img src="https://i.sstatic.net/OqHLa.png" alt="enter image description here"></p>

<p>Why is this statement true ?</p>

<p>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 ?</p>

<p><img src="https://i.sstatic.net/XzNAY.png" alt="enter image description here"></p>

CC BY-SA 3.0
2014-02-15T22:05:44.357Z
Which book *Introduction to Graph Theory*? Amazon UK lists at least five books with that exact title (Chartrand and Zhang, Trudeau, Voloshin, West, Wilson).
David Richerby
CC BY-SA 3.0
2014-02-16T00:03:04.367Z
From the image I think it's the one by West.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2014-02-16T07:03:06.273Z
The one by West 2nd edition
Shuzheng
<graph-theory>
Why is 2-connectedness characterized by the existence of an ear decomposition ?
Shuzheng
# Why is 2-connectedness characterized by the existence of an ear decomposition ?

(Asked by: username_0 on 2014-02-15)

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

![enter image description here](https://i.sstatic.net/OqHLa.png)

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](https://i.sstatic.net/XzNAY.png)

**Tags:** graph-theory

> **Comments:**
> **username_1**: Which book *Introduction to Graph Theory*? Amazon UK lists at least five books with that exact title (Chartrand and Zhang, Trudeau, Voloshin, West, Wilson).  
> **username_2**: From the image I think it's the one by West.  
> **username_0**: The one by West 2nd edition  

---

## 1 answers

### Answer by username_1 on 2014-02-15. Score: 6 | Accepted answer

"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.

> **Comments:**
> **username_0**: 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) ?  
> **username_1**: 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](http://diestel-graph-theory.com/basic.html)): 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.  
> **username_0**: Thank you David for clearing this out and for you reference online book.  
> **username_1**: 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!  
> **username_3**: There is a wikipedia article on ear decompositions that seems to make the same oversight as Wests' book (defining ear decompositions without requiring connectivity): http://en.wikipedia.org/wiki/Ear_decomposition  
> **username_1**: @Jim The wikipedia article's OK. If you track through the definitions, an "open ear decomposition" builds up the graph from cycle and a bunch of paths. Each of the paths must have as its endpoints distinct vertices of the graph built up so far, and the internal vertices must be disjoint from the graph build up so far. Both endpoints being pre-existing vertices enforces connectivity (and, by the theorem, 2-connectivity).  

---

