1

enter image description here

For question (b), I understand how to prove that they can't both contain an Eulerian trail--eulerian trail exists if and only if there are no more than 2 odd degrees of the vertices. So for a complete graph, each vertex will have a degree of 5 as it is connected to 5 other vertices, so K'+k=5.

However, this is a bit I'm stuck on. I know the argument that odd + even =odd / even +odd = odd, and using numbers like 3,2 /2,3 definitely satisifes and answers the question. But doesn't the argument fail if we use 1,4/4,1?

Please advise.Thank you in advance. And sorry for any wrong title labelling or tags.

Community
  • 1
CCC
  • 1,031

1 Answers1

2

According to eulerian trail/path : An undirected graph has an Eulerian trail if and only if exactly two vertices have odd degree, and if all of its vertices with nonzero degree belong to a single connected component.

Case_1 : We have given $6$ vertices, let degree sequence of graph $K$ has even degree of each vertices (i.e., number of odd degree vertex is $0$). So, $K$ would have eulerian trail by the definition.

But, complement of $K$(i.e. $K'$) would be odd degree of each vertex ($5 - even = odd$). So, $K'$ can not be eulerian trail by the definition.

Case_2 : We have given $6$ vertices, let degree sequence of graph $K$ has odd degree of exactly two vertices (i.e., number of odd degree vertex is $2$). So, $K$ would have eulerian trail by the definition.

But, complement of $K$(i.e. $K'$) would be odd degree of exactly three vertex ($5 - even = odd$). So, $K'$ can not be eulerian trail by the definition. Since $K'$ has more than $2$ odd degree vertices.

Comment : Case (b) is possible only when number of vertices are odd. (e.g., $C_n$).

Mithlesh Upadhyay
  • 4,787