0

I have the following question that I must prove or disprove:

Let =(,)be an undirected connected graph. Let be the minimum amount of edges one needs to add to G so that the resulting graph has an Euler cycle. Then x≤floor(n/2) when n=the number of vertices.

I believe this is untrue because if I have a graph of one vertex with an edge that connects to itself, then x=1 and floor(n/2)=0, so this statement cannot hold. However, I'm wondering if a one-vertex graph truly fulfills all the requirements. Is a one-vertex graph both undirected, connected and able to be considered a Euler cycle when it loops to itself? TIA.

liatkatz
  • 51
  • 5
  • 1) Check the definition of "graph" you were given in class and whether a "self-edge" is allowed. It's very possible that your definition of graph only allows for an edge between two distinct vertices, not from a vertex to itself. – Stef Jan 10 '23 at 09:11
  • 2) What makes you think that x=1 in the case of a graph with one vertex? x is the minimum amount of edges that you need to add to a graph so that it has a Eulerian cycle. Assuming self-edges are allowed, there are two possible graphs with one vertex: the graph with 1 vertex and no edge, and the graph with 1 vertex and 1 edge. What is x for each of these two graphs? – Stef Jan 10 '23 at 09:12

0 Answers0