Post a New Question

Discrete Mathematics

posted by on .

Let G be a graph with the vertex set V = {v1, v2, v3, v4, v5}.

If the degrees of the vertices are 5, 1, 0, 6, 2, respectively, does G have an Eulerian path? Why or why not?

  • Discrete Mathematics - ,

    An Eulerian path is a path which passes through ALL edges exactly once.
    This can happen if the graph has either 0 or 2 vertices with odd degrees.

    So even an incomplete graph (with degree 0 at one or more vertices) can have an Eulerian path.

  • Discrete Mathematics - ,

    MathMate: Is this correct then for the following problem:

    Let G be a graph with the vertex set V = [v1, v2, v3, v4, v5). If the degrees of the vertices are 5, 1, 0, 6, 2, respectively, does G have an Eulerian path? Why or why not?

    5 + 1 + 0 + 6 + 2 = 14

    2E = 14

    E = 7

    Yes, this problem does have an Eulerian path because it can have an odd degree or an incomplete graph can have the degree of 0 at one or more of the vertices.

Answer This Question

First Name:
School Subject:
Answer:

Related Questions

More Related Questions

Post a New Question