Math 316/416Problem Set I -- Solutions 22 February 2001

1. 1.4 #13; add (c) Must the complement of a disconnected graph be connected? Prove it or give a counterexample.
2. Show that every graph has two vertices with the same degree. [416 only: With a careful analysis, find all graphs with exactly one pair of vertices with the same degree.]
3. Determine whether the following two graphs are isomorphic. Prove it.
   $$\includegraphics [width=3in]{Syllabus-1.eps}$$

4. Find all nonisomorphic graphs with four vertices, proving that they are all nonisomorphic and that you have found all of them.

Solutions

1. 1. Find the appropriate modification of Euler's formula for a planar graph with c components.

      Let G be a disconnected graph, with v vertices, e edges, r regions, and c components. Denote the components by C₁, C₂, ..., C_c. From each component C_i choose a vertex v_i which borders the ``outer'' region. Add new edges between v₁ and v₂, v₃ and v₄,..., v_{c - 1} and v_c. The graph clearly remains planar when this is done, and the process adds no new regions or vertices. It results in a new graph G₁ which has the same number of regions and vertices as G, has e + c - 1 edges, and is connected. Hence, Euler's formula applies, and it gives

      r = (e + c - 1) - v + 2 $$\Rightarrow$$ r = e - v + c + 1

   2. Show that the corollary is valid for unconnected planar graphs.

      The corollary in the text applies to the graph G₁ created above, and gives e + c - 1 $\leq$ 3v - 6, where e, v, and c are as above. Since e $\leq$ e + c - 1 (a graph must have at least one component; indeed, an unconnected graph has at least two), we have e $\leq$ e + c - 1 $\leq$ 3v - 6, proving the corollary for G.

   3. Must the complement of a disconnected graph be connected? Prove it or give a counterexample.

      Choose two vertices v₁ and v₂ in the disconnected graph G. Either they are in the same component, or they are in different components. If they are in the same component, then let w be a vertex in a different component (which exists because we are assuming the graph is disconnected). Then in the graph $\overline{G}$, (v₁, w) and (v₂, w) are edges. So the path v₁, w, v₂ connects v₁ and v₂ in $\overline{G}$.

      If v₁ and v₂ are in different components of G, then (v₁, v₂) is an edge in $\overline{G}$, and so v₁, v₂ is a path connecting them in $\overline{G}$.

2. Let the graph G have n vertices. The largest degree which a vertex can have in such a graph is n - 1, as there are only n - 1 other vertices for it to possibly be adjacent to. The smallest possible degree is 0.

   Assume that G has all vertices of different degrees. Then there must be one vertex for each possible degree, 0, 1,..., n - 1. Denote the vertex of degree i by v_i, for 0 $\leq$ i $\leq$ n - 1. Since deg(v_{n - 1}) = n - 1, v_{n - 1} must be adjacent to every other vertex. But then deg(v₀) $\geq$ 1, which is a contradiction. So our assumption that all the vertices of G must have different degrees is false; that is, G has at least two vertices with the same degree.

3. The graphs are isomorphic. See a labelling of the vertices below which shows an isomorphism (there are many). You should check that the labelling does preserve adjacency -- that is, that (for example) A is connected to the same vertices (B, E, and 1) in both graphs.
   $$\includegraphics [width=4in]{PS1Solutions-1.eps}$$

4. Find all nonisomorphic graphs with four vertices.

   There are 11 of them: 1 with no edges, 1 with one edge, 2 with two edges, 3 with three edges, 2 with four edges, 1 with five edges, and 1 with six edges.

   You could have simplified work by just working with 0, 1, 2, or 3 edges, and noting that something with 4 edges is the complement of something with 2 edges, for instance.