Question

Answer #1

Given

G is regular graph with vertices n=13

Order =6 and by definition of regular graph

Degree of each vertex=6

Now by theorems stated below:

Dirac Theorem- “If G is a simple graph with n vertices with n>=3 such that the degree of every vertex in G is at least n/2, then G has a Hamiltonian circuit.”

Ore’s Theorem- “If G is a simple graph with n vertices with n>=3 such that deg(u) + deg(v)>=n for every pair of non-adjacent vertices u and v in G, then G has a Hamiltonian circuit.”

Since 6<13/2

Also 6+6<13

So this doesn't satisfy both Dirac and ore's theorem.

Therefore G doesn't have a Hamiltonian circuit.

Hope you get your answer. Thank you and please like the answer

a. A graph is called k-regular if every vertex has degree k.
Explain why any k-regular graph with 11 vertices must conain an
Euler circuit. (Hint – think of the possible values of k). b. If G
is a 6-regular graph, what is the chromatic number of G? Must it be
6? Explain

Q. a graph is called k-planar if every vertex has degree
k.
(a) Explain why any k-regular graph with 11 vertices should contain
an Euler’s circuit.
(what are the possible values of k).
(b) Suppose G is a 6-regular graph. Must the chromatic number of G
be at leat 6? Explain.

A K-regular graph G is a graph such that deg(v) = K for all
vertices v in G. For example, c_9 is a 2-regular graph, because
every vertex has degree 2. For some K greater than or equal to 2,
neatly draw a simple K-regular graph that has a bridge. If it is
impossible, prove why.

Prove or disapprove each of the following:
(a) Every disconnected graph has an isolated vertex.
(b) A graph is connected if and only if some vertex is connected
to all other vertices.
(c) If G is a simple, connected, Eulerian graph, with edges e, f
that are incident to a common vertex, then G has an Eulerian
circuit in which e and f appear consequently.

Supposed G is a graph, possibly not connected and u is a vertex
of odd degree. Show that there is a path from u to another vertex v
6= u which also has odd degree.(hint: since u has odd degree it has
paths to some other vertices. Just consider those.)

A graph is k-colorable if each vertex can be assigned one of k
colors so that no two adjacent vertices have the same color. Show
that a graph with maximum degree at most r is (r +
1)-colorable.

Draw an undirected graph with 6 vertices that has an Eulerian
Cycle and a Hamiltonian Cycle. The degree of each vertex
must be greater than 2. List the degrees of the
vertices, draw the Hamiltonian Cycle on the graph and give the
vertex list of the Eulerian Cycle.
Draw a Bipartite Graph with 10 vertices that has an Eulerian
Path and a Hamiltonian Cycle. The degree of each vertex
must be greater than 2. List the degrees of the
vertices, draw the Hamiltonian Cycle...

Supposed G is a graph, possibly not connected and u is a vertex
of odd degree. Show that there is a path from u to another vertex v
does not equal u which also has odd degree.(hint: since u has odd
degree it has paths to some other vertices. Just consider
those.)

Let G be a graph where every vertex has odd degree, and G has a
perfect matching. Prove that if M is a perfect matching of G, then
every bridge of G is in M.
The Proof for this question already on Chegg is wrong

Prove that every graph has two vertices with the same degree.
(hint: what are the possible degrees?)

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 11 minutes ago

asked 21 minutes ago

asked 22 minutes ago

asked 35 minutes ago

asked 41 minutes ago

asked 42 minutes ago

asked 49 minutes ago

asked 56 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago