What is the upper bound for edges that are not going in or out of node 1 in this graph?

38 Views Asked by At

I have the following graph with the following problem:

We want to obtain a Hamiltonian cycle by supplying all nodes with 1 unit of flow. Initially the node 1 will send 4 units of flow through one and only one of its edge to the next node. The next node consumes 1 unit of flow and sends the rest through one and only one of its edge to the next node and so on until we arrive back at node 1. Node 1 will then consume the last unit of flow.

The upper bound of flow that you can send through one of the edges going out of node 1 is 4 units and the upper bound of flow that comes back through one of the edge to node 1 is 1 unit. I want to know what would be the upper bound of flow that can be sent on edges that are not connected to node 1.

graph

1

There are 1 best solutions below

0
On

An upper bound is $3$, more generally $n-1$ for a graph with $n$ nodes.