Discrete Mathematics

posted by .

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.

Respond to this Question

First Name
School Subject
Your Answer

Similar Questions

  1. Math

    Prove that a simple graph with n >_ 2 vertices must have atleast two vertices with the same degree. There was a hint given in the book saying that the key to this is the graph can not have both a vertex of 0 degree and a vertex …
  2. Math

    Prove that a simple graph with n >_ 2 vertices must have atleast two vertices with the same degree. There was a hint given in the book saying that the key to this is the graph can not have both a vertex of 0 degree and a vertex …
  3. heelp math

    A graph is constructed iteratively according to the following algorithm. The graph starts as a single vertex. With probability p, the graph stops here. Otherwise, 3 new vertices are constructed and joined to this vertex. If we have …
  4. Discrete Mathematics

    Consider the complete graph with 5 vertices, denoted by K5. A. Draw the graph. B. How many edges are in K5?
  5. Discrete Mathematics

    Let G be a graph with vertex set V = {v1, v2, v3, v4, v5}. A. Is it possible for the degrees of the vertices to be 3, 6, 2, 1, 5, respectively?
  6. Discrete Mathematics

    Using Fleury's Algorithm in the graph to the bottom left, I deleted three edges and I got the graph to the bottom right. If I am currently at the starred vertex, list all possibilities for the edge I should travel next.
  7. Discrete Mathematics

    Let G be a graph with vertex set V = { v1, v2, v3, v4, v5}. Is it possible for the degrees of the vertices to be 3, 6, 2, 1, 5, respectively?
  8. Discrete Mathematics

    Let G be a graph with vertex set V = {v1, v2, v3, v4, v5}. If the degrees of the vertices are 1, 2, 3, 4, 6, respectively, how many edges are in G?
  9. Discrete Mathematics

    Let G be a graph with vertex set V = { v1, v2, v3, v4, v5}. If the degrees of the vertices are 1, 2, 1, 3, 1, respectively, is G a tree?
  10. Discrete Mathematics

    Using Fleury's Algorithm in the graph to the bottom left, I deleted three edges and I got the graph to the bottom right. If I am currently at the starred vertex, list all possibilities for the edge I should travel next.

More Similar Questions