2
$\begingroup$

Just introduced to graph theory, I am asked whether or not there can be constructed a simple graph with six vertices, of degrees $4,4,4,2,1$ and $1$. According to my textbook and my drawing skills, there can not be such a graph, but I have trouble explaining why that is. The sum of the degrees gives $16$, so the number of the edges must be $8$, and that alone doesn't prevent the graph from being possible (consider a parallelogram with its diagonals drawn - the two extra vertices are at the midpoints of two parallels). Also, so far we only have concluded that the number of vertices with an odd degree must be even, and in this case I can't make use of it.

I also thought that maybe I should manipulate the problem to use the pigeonhole principle, but I can't find a way to manipulate the problem to do so. I did it in two certain combinations, but obviously I can't list all possible (attempted) graphs to show that the principle applies.

Any help would be greatly appreciated! Thanks in advance!

$\endgroup$
1
  • $\begingroup$ For a simple graph, $G=(V,E)$ Note: $e$ here stands for number of edges (1) $\sum_{v_i \in v}deg_G(v_i)=2\times e$ (2) For a graph with $n$-vertices, $M,m$ are the maximum and minimum degree of the vertices,$m\le\frac {2e}{n}\le M$ (3) Maximum number of edges in a graph with $n$-vertices are $\frac{n(n-1)}{2}$ (4) Maximum degree of a vertex in a graph with $n$ vertices is $n-1$ (5) The number of vertices with odd degree must be even. These should be helpful $\endgroup$
    – whatamidoing
    Commented Nov 16, 2023 at 8:55

3 Answers 3

Reset to default
5
$\begingroup$

In this case, you can just argue directly. Start with the vertices of degree 4. Those have to be connected to at least one of the vertices of degree 1, since there are only 3 other vertices they could be connected to. But there are 3 degree 4 vertices and only 2 degree 1 vertices, and each degree 1 vertex can only connect to one degree 4 vertex. So you can't fit everything in.

$\endgroup$
1
  • 1
    $\begingroup$ I see, so in essence it is indeed the pigeonhole principle, but with the right manipulation, say, the right order of looking at the graph. I had the same reasoning, that I can't fit all in, but I was stuck thinking "so the three vertices of degree 4 must be connected to each other, because if they are not, [.....], and so [....], " etc. This is indeed straight-forward. I guess, with time and practice comes the intuition. Thanks very much!! $\endgroup$
    – John0207
    Commented Nov 14, 2023 at 17:47
2
$\begingroup$

The approach that was probably intended for this problem is the Havel-Hakimi algorithm, which proceeds as follows for your instance: $$ \color{red}{4},4,4,2,1,1 \\ 4-1,4-1,2-1,1-1,1 \\ 3,3,1,0,1 \\ \color{red}{3},3,1,1,0 \\ 3-1,1-1,1-1,0 \\ 2,0,0,0 $$

An alternative approach uses the Erdos-Gallai theorem.

$\endgroup$
1
$\begingroup$

Assume for contradiction that such a graph exists. Label the 6 nodes alphabetically in descending order of degree:

$$A : 4, B : 4, C : 4, D : 2, E : 1, F : 1$$

Let's enumerate all the possibilities for how E and F use their one connected edge.

  • E and F are connected to each other, and ABCD is a separate graph of degrees $\{ A : 4, B : 4, C : 4, D : 2 \}$, with 7 total edges.
  • E and F are both connected to D, which makes DEF disconnected from graph ABC with degrees $\{ A : 4, B : 4, C : 4 \}$, with 6 total edges.
  • One of $\{E, F\}$ (WLOG, assume F) is connected to D, and the other one (E) is connected to one of the degree-4 nodes (WLOG, assume C). Subtracting the known edges DF and CE from the degree counts, we're left with $\{A : 4, B : 4, C : 3, D : 1\}$, with 6 total edges.
  • Both E and F are connected to nodes of degree 4. WLOG, assume that E is connected to B, and F is connected to C. This leaves the degree counts $\{A : 4, B : 3, C : 3, D : 2\}$, with 6 total edges.

Note that regardless of how we connect E and F to the rest of the graph, we're left with the subgraph ABCD having at least one node of degree 4 (A). However, a graph with 4 nodes cannot have any nodes with degree higher than 3. (If it did, then one pair of nodes would be connected by multiple edges, making the graph not “simple” by definition.)

Therefore, a graph with the given node degrees cannot exist.

$\endgroup$
2
  • 1
    $\begingroup$ This is an elegant answer, thank you. A question; could we "subtract" the vertices $E$ and $F$ from the graph, along with their respectives edges, and claim that this leaves us with points $A,B,C$ and $D$, of which at least one has a degree of 4? I mean, instead of listing all the possibilities, claim that, since we take away two edges, regardless of where they where connected to, we can't "reduce" all 4-degree points to 3. Not that your thoroughness was for nothing, it was really helpful, I'm just curious if a shorter answer would be accepted. Thanks a lot nevertheless! $\endgroup$
    – John0207
    Commented Nov 14, 2023 at 18:11
  • 1
    $\begingroup$ @John0207: Yeah, that would work too. $\endgroup$
    – Dan
    Commented Nov 14, 2023 at 19:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .