Happy new year to all!
Could you explain me with this task from my Discrete Mathematics examination?
Suppose is a simple undirected graph with vertices, each having degree 5.
a) For which values of does this make sense?
b) For which values of does the graph have a Euler path?
c) What is the smallest value of for which the graph might be planar?
Thanks in advance!
a) The maximum degree of a simple undirected graph with $n$ vertices is $n-1$, so we must have $n-1 \geq 5 \implies n \geq 6.$ One can also check that $K_6$ satisfies the assumptions, so $n \geq 6$ is a tight necessary condition.
Note: My original post stated that $n \geq 6$ is sufficient. As Shahab pointed out in the comments, this is false since $n$ cannot be odd. I believe $n \geq 6$ and $n$ even is necessary and sufficient, but you may want to check this.
b) An Euler path requires all but possibly two vertices to have even degree. Since $n \geq 6$ vertices have odd degree, it cannot have an Euler path.
c) Since the number of edges $e = \frac{5n}{2}$ and for a simple undirected planar graph $e \leq 3n - 6,$ we have $n \geq 12.$ This is a necessary condition, but I bet you can find an example with $n=12,$ showing it is also sufficient.