Determine if a graph with the following characteristics exists or not

41 Views Asked by At
  1. A graph of order 13 where the vertices $v_1,...,v_{13}$ have the following degrees: $v_i$ has degree $3$ if $i$ is odd, $4$ if $i$ is even
  2. A graph of order 12 where the vertices $v_1,...,v_{12}$ have the following degrees: $v_i$ has degree $1$ if $i$ is odd, $2$ if $i$ is even

I tried to answer this question by simply using the handshaking lemma.

  1. Between 1 and 13 there are seven odd numbers which mean seven vertices that have odd degrees. By the lemma, we know that in a graph there is an even number of vertices which have an odd degree. The graph doesn't exist.
  2. Using the same reasoning a graph of this type should exist.

Could you confirm if my reasoning is correct? If correct, is it sufficient to answer the question or should I include additional proof?

1

There are 1 best solutions below

2
On BEST ANSWER

The handshake lemma works well for showing that a list of degrees is impossible, but it's a one-way implication. Your part (1) is good, but your reasoning for part (2) simply doesn't prove anything. For example, a list of degrees $4,4,4,0,0,0$ on six vertices satisfies the handshake lemma condition, but there is no such graph.

For part (2), the best way to prove such a graph exists is to explicitly construct such a graph.