– 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…
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.
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.
Best Answer
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$.