Question

Suppose a connected graph has 15 labeled nodes, given that it has an eularian circuit, what is the minimum number of distinct circuits which it must have? [Note : the circuit a->b->c->a is not same as b->c->a->b]

Comments

will it be 15! ?

---

i think only 15.
we can form 15 circuits if the graph itself is a cycle with 15 vertices and 15 edges(as it is given  the circuit a->b->c->a is not same as b->c->a->b, 15 circuits in minimum are possible)

---

what about max?

Answer 1

MINIMUM NUMBER OF DISTINCT CIRCUITS ,CONSIDER MINIMUM NO OF EDGES IN THE GRAPH.

if a graph contains four vertices{a,b,c,d}.connected edges are a-b,b-c,c-d,d-a.and it contains eularian circuit.

minimum no of circuits are a-b-c-d-a,,b-c-d-a-b,,c-d-a-b-c,,d-a-b-c-d.

for 'n' no of vertices graph contains minimum of 'n' circuits.

Comments

according to me also,answer should be 15 but answer given is 30.i guess that because a-b-c-d-a as well as a-d-c-b-a ,,and hence for all the remaining three.

hence,answr is 30.

i have one doubt,in euler path or circuit,during the path,we can cross 1 vertex more than once..right??(i am not talking about starting and end vertex,i am asking abt something in the middle)

---

any idea about max no. of circuits??

---

yes,in eular circuit visiting vertex is more than once but not edge.

---

max no of circuit varies from graph to graph.if a graph contain four vertices max no of circuits also 8.

but if the graph contains more no of vertices  i don't know formula,manually construction is one possible.

Answer 2

We can call the Eulerian circuit that exists n1, n2, ….., nk. Then, k>=15

because every node must be in the Eulerian circuit. Furthermore, we can create Eulerian circuits at will simply by taking ni, ni+1, ….,nk, n1, n2, …, ni-1, ni  or ni, ni-1, ….,n1, nk, …, ni+1, ni,alternatively , which creates a guaranteed 30 Eulerian paths (lower bound for the minimum). We can show that this is an achievable minimum by considering the graph that consists of 15 nodes on a circle with adjacent nodes having an edge in between them. 

 

Since this graph only has 30 Eulerian circuits, this is indeed the fewest we can do.