Graph Theory

ex 1.5.12 (a) (first edition), ex 1.5.11 (a) (second printing)

carmela — Mon, 05 Oct 2009 20:09:17 +0000

I think that we should require that the graph has no isolated vertices, because then if it is arc-transitive it has to be both vertex and edge transitive.

Open problem 70

Justin — Sun, 27 Sep 2009 21:04:26 +0000

I would like background information concerning open problem 70. I cannot find the reference S. Thomassé 2005, nor can I find any mention of the conjecture in Sullivan 2006. Thanks.

Ex 10.3.6 (c)

carmela — Thu, 17 Sep 2009 09:06:59 +0000

I am still battling with this part. Please check the details written in the text: the Turan graph (2,12) is actually the complete bipartite graph K(6,6), while the icosahedron is not bipartite.

page 317 (first edition), page 321 (second printing)

Justin — Thu, 17 Sep 2009 09:00:22 +0000

The last sentence of the first paragraph is missing a full stop.

Exercise 1.4.6a

Adrian Bondy — Fri, 11 Sep 2009 21:10:04 +0000

Contributed by Jeannette Dooley.

The graph H should be formed by joining the first and fourth (not first and third) vertices of P.

Hint to ex 4.2.5 (b)

carmela — Wed, 02 Sep 2009 14:21:11 +0000

I think that the equation that appears in the hint to ex 4.2.5 (b) is wrong, because w4=45, w3=16, f4=8, f3=3. Please check.

Hint to ex 4.1.15

carmela — Wed, 02 Sep 2009 14:20:12 +0000

I suggest to use induction on n, but instead of deleting the root, delete a leaf at maximum distance from x, and such that its predecessor has minimal degree. Please let me know if that could work out.

Proof of Theorem 10.26 (clarification).

Adrian Bondy — Mon, 17 Aug 2009 22:47:00 +0000

Contributed by Yaad Blum.

In Case 2, one cannot apply Exercise 9.2.3 directly, as the union of B and C might be separable.

Proof of Lemma 10.33

Adrian Bondy — Mon, 17 Aug 2009 22:29:59 +0000

Contributed by Yaad Blum.

The term G+e should be replaced by H+e (twice).

Exercise 14.2.9

Adrian Bondy — Mon, 17 Aug 2009 22:21:54 +0000

Contributed by Yaad Blum.

It must be assumed here that k is at least three. The Hajos join of two 2-critical graphs is not 2-critical.