Question

Recall the definition of the degree of a vertex in a graph. a) Suppose a graph has 7 vertices, each of degree 2 or 3. Is the graph necessarily connected ?

b) Now the graph has 7 vertices, each degree 3 or 4. Is it necessarily connected?

My professor gave an example in class. He said triangle and a square are graph which are not connected yet each vertex has degree 2.

(Paul Zeitz, The Art and Craft of Problem Solving )

Θθ 100% ト ④ (123 of 383) 107 0 107 (123 of 383) ns. 4.1. Graph The Connectivity and Cycles Now that we see how graph theory can completely recast a problem, we shall investigate some sim- ple properties of graphs, in particular the relationship between the number of vertices and edges and the existence of cycles. The number of edges emanating from a particular vertex is called the degree of the vertex. If the vertex is x, the degree is often denoted by d(x). You should easily be able to verify the following important fact, often called the handshake lemma (if you want a hint, reread Example 3.4.7 on page 90). In any graph, the sum of the degrees of all the vertices is equal to rwice the number of edges. A graph is connected if for every pair of vertices, there is a walk from one to the other. If a graph is not connected, one can always decompose it into connected components. For example, the graph below has 10 vertices, 11 edges, and two connected components. Observe that the handshake lemma does not require connectivity: in this graph, the degrees (scanning from left to right, from top to bottom) are 1.2.1, 1,3,3,2.4,3.2. The sum is 22 2-11 A connected graph that contains no cycles is called a tree. For example, the following 8-vertex graph is a tree.

Answer 1

If a graph has 7 vertices where every vertex has degree 2 or 3 then it need not be connected. For example, it may be a cycle of length 7 (a septagon in which every vertex has degree 2) or it may be a square and a triangle which are its two connected components

If a graph has 7 vertices where every vertex has degree 3 or 4. If it has 2 connected components of sizes then as the degree of a vertex in a fully connected component of size m is (m-1), the minimum degree of all vertices must be $\min\{m-1,n-1\}\geq 3\Rightarrow m-1,n-1\geq 3\Rightarrow m\geq 4,n\geq 4$

We also must have $m+n=7$ as the two components of sizes make up the entire graph

Clearly, the conditions $m+n=7$ and $m\geq 4,n\geq 4$ are not compatible

So any graph with 7 vertices where each vertex has degree 3 or 4 must be a connected graph