Realizability of Graphs
Realizability of Graphs
Suppose that we are given a certain degree sequence. Is it then possible to construct a graph that has this degree sequence? In general, the answer is no. Such degree sequences that we can construct graphs for are defined below.
Definition: The sequence $(d_1, d_2, d_3, ..., d_n)$ is said to Realizable or Graphic if and only if there exists a graph $G = (V(G), E(G))$ such that $|\: V(G) \:| = n$, AND for each $x_j \in V(G)$, $\deg(x_j) = d_i$. |
For example, let's consider the sequence $(9, 2, 2, 1)$ for a simple graph. Is this realizable? The answer is NO. There are only $4$ vertices in this sequence, and the highest degree is $9$. That would imply that there exists a vertex attached to $9$ other vertices, which is impossible.