4
$\begingroup$

Is there a (simple) graph $\Omega=(\{\alpha_1,\alpha_2,...,\alpha_9\},\Omega_K)$ with $$(\text{deg}(\alpha_1),\text{deg}(\alpha_2),...,\text{deg}(\alpha_9))=(6,6,6,6,5,3,3,3,3)$$

Some additional information:

A graph is a pair $G = (V, E)$, where $V$ is a set whose elements are called vertices, and $E$ is a set of paired vertices, whose elements are called edges.

The edges of a graph define a symmetric relation on the vertices, called the adjacency relation. Specifically, two vertices $x$ and $y$ are adjacent if $\{x, y\}$ is an edge. A graph may be fully specified by its adjacency matrix $A$, which is an $n \times n$ square matrix, with $A_{ij}$ specifying the number of connections from vertex $i$ to vertex $j$. For a simple graph, $A_{ij}\in \{0,1\}$, indicating disconnection or connection respectively, meanwhile $A_{ii}=0$.

As I am currently learning for my discrete maths exam, I am looking at old exam questions. Unfortunately I'm not really sure where to start here. Thanks in advance!

Does a simple graph with $(\text{deg}(\alpha_1),\text{deg}(\alpha_2),...,\text{deg}(\alpha_9))=(6,6,6,6,5,3,3,3,3)$ exist.

$\endgroup$
3
  • 4
    $\begingroup$ Handshaking Lemma $\endgroup$
    – user700480
    Commented Jun 20, 2022 at 15:30
  • 1
    $\begingroup$ In general this is graph realization problem $\endgroup$
    – Sil
    Commented Jun 20, 2022 at 16:15
  • 2
    $\begingroup$ No. Regardless of whether or not the graph is simple, the sum of the vertex degrees must be san even number. $\endgroup$
    – bof
    Commented Jun 21, 2022 at 8:19

2 Answers 2

4
$\begingroup$

This cannot be realized because edges have two endpoints while the edges in a graph with degree sequence $(6,6,6,6,5,3,3,3,3)$ would have a total of $$6+6+6+6+5+3+3+3+3 = \text{an odd number}$$ of end points.

$\endgroup$
3
$\begingroup$

It cannot. See the algorithm here. Essentially, you order the degrees in descending order and then draw edges from the node with the most edges to the ones with the most edges. Once you've done that, you remove the current node and subtract one from the number of edges required of the remaining nodes that had an edge drawn to them. If you reach $0$, the graph can be realized, but if you are left with something that requires a further edge, the graph doesn't work. Here we have:

$$6,6,6,6,5,3,3,3,3$$

The first entry is 6, so draw an edge to the next 6 nodes and remove the first node.

$$6-1,6-1,6-1,5-1,3-1,3-1,3,3\\ =5,5,5,4,2,2,3,3$$

We must then reorder this in descending order:

$$5,5,5,4,3,3,2,2$$

Proceeding, we get:

$$4,4,3,2,2,2,2\\ 3,2,1,1,2,2\\ (reorder)3,2,2,2,1,1\\ 1,1,1,1,1\\ 1,1,1\\ 1$$

$\endgroup$

You must log in to answer this question.

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