HW8 21-484 Graph Theory SOLUTIONS (hbovik) - Q

1: Determine, with proof, the edge-chromatic number of the Petersen graph.

The Petersen graph has maximum degree 3, so by Vizing’s theorem its edge-chromatic number is 3 or 4.
We will prove that in fact the edge-chromatic number is not 3, by considering possible 3-edge-colorings
and finding contradictions.
First, we pick a vertex x and say that its edges are colored 1, 2, and 3 WLOG. Let y be the neighbor
along the 3 edge, and let z be the neighbor on the 2 edge. y has two other edges, and we consider
two cases where they are numbered 1, 2 and 2, 1. z has two other edges, and we consider two other
cases where those are numbered 1, 3 and 3, 1. Combining these cases gives 4 cases. In all 4 cases,
we can fill in forced edge colors until there is a contradiction [the order in which you force edges will
affect which edges are colored and which are uncolorable in the end, but in any case you find a partial
coloring forced by the assumptions that cannot be extended to a proper coloring]. We display the the
initial assumption, then the four cases, and then the forced colors. This proves χ0 (G) = 4.

2 3

2
1 1 1
2
3 3
1 2 1 3 2
2 z 2 z
1 1
x 3 y x 3 y

3 1

3 2 3 2
3
1 3 1
1 2 1 2
2 z 2 z
1 1
x 3 y x 3 y
1
2 z

2 3
x y
3
1 (or 3) 1 3 2
1
2
3 3
1 1 1 1
2 z 2 z
2 2
x 3 y x 3 y

3 1 2

3 2 3 3

1 1 1
(or 3)
1 1 1 1
2 z 2 z
2 2
x 3 y x 3 y

1
HW8 21-484 Graph Theory SOLUTIONS (hbovik) - Q

2: Show that no regular, self-complementary graph has edge-chromatic number equal to its maximum
degree.

An r-regular self-complementary graph has r = n−1 2 (since n − 1 − r = r). Because r is an integer, n

is odd. Odd order regular graphs are all class 2 because each vertex must be missing a color in any
edge-coloring, so a ∆(G)-edge-coloring is not possible.

2
HW8 21-484 Graph Theory SOLUTIONS (hbovik) - Q

3: Show that no regular graph with a cut vertex has edge-chromatic number equal to its maximum
degree.

We show the contrapositive, that a regular class 1 graph has no cutvertex.

Let G be a regular graph with vertex v and let ϕ be a ∆-edge-coloring of G. Let x and y be neighbors
of v. Let α = ϕ(vx) and let β = ϕ(vy). In G − v, x is missing α (and y is missing β). Let P be the α/β
path starting at x. We prove that P ends at y: No vertex besides x and y is missing α or β in G − v,
because the edges of v besides vx and vy cannot be colored α or β, and in G no vertex is missing any
color. x is missing only α, because its other edges remain in G − v. Therefore, the last vertex of P
cannot be x (it has a β edge), and it cannot be any vertex other than x and y (they have an α edge
and a β edge), so the path ends at y.
Because any two neighbors of v have a path between them in G − v, v is not a cut-vertex! Suppose a0
and b0 are connected in G and disconnected in G − v; let P be an a0 –b0 path; v lies on P (otherwise P
is an a0 –b0 path in G − v), so call a and b the neighbors of v on P (with a closer to a0 and b closer to
b0 ). There is an a–b path in G − v, Q, and so a0 P aQbP b0 is an a0 –b0 path in G − v.

3
HW8 21-484 Graph Theory SOLUTIONS (hbovik) - Q

4, Diestel 7.4: Determine the value of ex(n, K1,r ) for all r, n ∈ N.

First, observe that if n ≤ r, no graph with n vertices contains a star graph on r + 1 vertices, so in this
n


case, the extremal number is 2 , the maximum number of edges a graph can have.
In the non-trivial case, we will show that the extremal number is b n(r−1)
2 c. The idea is that this is the
number of edges we get from a (r − 1) regular graph. Such a graph is clearly edge-maximal without a
r-star, and moreover, it is extremal, as every vertex is contributing as much as it possibly can without
creating an r-star. (You can also see this as any graph with more edges would have to have a vertex
of degree r by averaging, so at least, our bound is an upper bound on the extremal number. The rest
of the proof is showing that the upper bound can be realized.)
First, let’s assume n(r − 1) is even. This is when we won’t need a floor. Let’s start with an n-cycle,
which is 2-regular. (If r = 1, the graph can not have edges so the bound is trivial.) For every i in
2 ≤ i ≤ b r−1
2 c, we will add an edge between every vertex at distance i on the original cycle. If (r − 1)
is even, we have created an r − 1 regular graph, as desired. Otherwise, we have an (r − 2) regular
graph, and n has to be even. In this case, we will add edges between all vertices that are at a distance
n
2 from each other. Observe that these additional edges give us a perfect matching. So every degree
increases by 1 to give us an (r − 1) regular graph, and we are again done.
So now we just have to worry about the case when both n and (r−1) are odd. The previous construction
can be used to create an r − 2 regular-graph, and we add a perfect matching of edges between pairs of
n − 1 of the vertices, leaving exactly one vertex of degree r − 2. Thankfully, the resulting graph also
matches our bound, and is extremal since there is no graph with total degree being odd.