Graph Theory: A loop-free connected graph with degree sequence

Question

- Background Information:

I am studying graph theory in discrete mathematics. As I was practicing questions I came across this solution, provided by my professor, which is confusing for me to fully understand it. I need some clarification for the solution to make sense

---

- Question and Solution:

Construct a graph with the specified properties. If no such graphs exist, explain why.

---

- My question:

Could you please explain...

1. Why can we have a maximum of 2 nodes of degree 1? In the degree sequence, there are 3 nodes of degree 1, so I don't understand where the 2 is coming from.

2. Why does the graph not exist? If we add the degree sequences, we get a sum of 24 which is even and acceptable for drawing the graph.

---

• Edit: [definitions]

A loop is an edge from a vertex to itself.

Answer 1

There is a node of degree $7$ that is joined to all the other nodes. Now consider the node of degree $5$ ... how many nodes of degree $1$ are now possible ?

Answer 2

I think if I answer your first question, second one will be answered automatically.

Suppose for a contradiction that given graph exists. Then since one vertex out of eight has degree $7$, this vertex is connected all other vertices. Now, consider the vertex with degree $5$, which has one edge connected to the vertex with degree $7$. Also notice that remaining four edges must be connected to a vertex. But this is impossible since we already have $3$ vertices with degree $1$ and connected to the vertex with degree $7$, which is a contradiction as required (you can find the reason why we must have two vertices with degree $1$, of course without making the sum of degrees odd).

Answer 3

The degree $7$ node, which I'll denote $v_1$, connects to all $8-1=7$ other nodes.

One of those must be the degree $5$ node, which I'll denote $v_2$, and $v_2$ connects to $5$ other nodes distinct from $v_2$, at most $1$ of which can be $v_1$ itself.

So, at least $4$ of the nodes that $v_2$ connects to are also nodes that $v_1$ connects to, and these nodes all therefore have valence $\ge 2$.

Of the seven nodes that $v_1$ connects to, one of them is $v_2$ which has valence $4$, and we've shown that at least $4$ others of them have valence $\ge 2$. That leaves at most $2$ which have valence $1$.

Answer 4

This is not true unless the graph is free of multiple edges as well.

This is true for simple graphs as shown by other answers.