A simple graph G has $14$ vertices and $85$ edges. Show that G must have a Hamilton circuit but does not have an Euler circuit.
My attempt:
to be hamilton circuit, each should have degree at least $n/2$ so total degree should be $n\times {n\over 2} = 98$. Total degree of the graph is $85\times 2 = 170 \gt 98$ so it has Hamilton circuit. But how can I prove it has no Euler circuit?
Show that the regions of a planar graph cannot be properly colored with $2$ colors if the graph has $9$ vertices and $17$ edges and the degree of each vertex is at least $3.$
My attempt: I know there are $10$ regions but how to make use of the second piece of the info$?$ I know how to proceed
To show that the graph is not Eulerian, we argue that there must be a vertex of odd degree.
To do so, suppose for contradictory purposes that every vertex was of even degree.
By the handshaking lemma (or first theorem of graph theory) we have:
$$\sum\limits_{v\in V}\deg(v) = 2|E|$$
In the case that every degree was even, and there are an even number of vertices, we will have the left hand side is divisible by four. HOWEVER, the right hand side is equal to $2\cdot 85$ which is not divisible by four, a contradiction. Therefore there must be at least one vertex of odd degree.
By theorem, a graph is Eulerian if and only if it is connected and has no vertices of odd degree. Since there is at least one vertex of odd degree, the graph is not Eulerian and therefore has no Eulerian circuit.
For why the graph is or is not Hamiltonian, you attempted to use Dirac's Theorem, which says if a simple graph with $n\geq 3$ vertices has every vertex of degree $\frac{n}{2}$ or greater, then the graph is Hamiltonian.
What you have shown by your calculations is that the average degree is greater than $\frac{n}{2}$ but you have not shown that every degree is greater than $\frac{n}{2}$.
To prove that every degree is greater than $\frac{n}{2}$, suppose otherwise that there is some vertex of degree $6$ or less. Let us call this vertex $v$. The most number of edges possible that don't touch $v$ will be $\binom{13}{2}=78$. Adding in the most number of possible edges for $v$ will bring the total up to a maximum of $78+6=84$ which is strictly less than the number of edges $85$, a contradiction. Therefore every vertex must be of degree at least $7$ and Dirac's theorem applies, showing that the graph is indeed Hamiltonian.