A strongly connected directed graph has 12 vertices and is required to have the minimum possible number of edges. How many edges are necessary?
A directed cycle through all 12 vertices is strongly connected and uses exactly 12 edges.
In a flow network, an s-t cut has crossing capacities 7, 11, 5, and 9. What is the cut capacity?
Cut capacity is the sum of capacities of directed edges from S to T: 7+11+5+9 = 32.
A flow network has source s with outgoing capacities 8, 13, and 6. What is the largest possible value of any s-t flow?
By the source cut, flow value cannot exceed 8+13+6 = 27.
A connected graph has 20 vertices and 23 edges. How many independent cycles does it contain, i.e. what is its cyclomatic number E-V+1?
For a connected undirected graph, cyclomatic number is E-V+1 = 23-20+1 = 4.
$A complete graph K_{7} has how many distinct spanning trees?$
By Cayley’s formula, $K_{n}$ has $n^{n-2}$ spanning trees. Thus $7^5$ = 16807.