Question

For each of the following, either draw a graph or explain why one does not exist:

a) Circuit-free graph, 6 vertices, 4 edges

b) Graph, 5 vertices, all of degree 3

c) Complete graph, 4 vertices, has an Euler circuit

d) Complete graph, 4 vertices, has a Hamiltonian circuit

Answer 1

For Option a) and d) The graphs are

b) The graph is not possible;

As we know that the sum of all the degrees is equal to twice the number of edges. So the sum of the degrees must be even.

Here Number of vertices is 5 and each vertex has degree 3

So the sum of degrees is

So the graph is not possible

c) The graph is not possible;

Since a complete graph of 4 vertices has odd degree at each vertex, so no Euler Circuit is possible.

As a Euler circuit has all vertices of even degree.