Graphs · step 11 of 14

Directed graphs, in-degree & out-degree

In a digraph each edge has a direction, so every vertex has an in-degree and an out-degree, and both sums equal |E| — not 2|E|. Connectivity splits in two: weakly connected means the underlying undirected graph is connected, strongly connected means every vertex reaches every other along directed edges. A digraph with no directed cycle is a DAG, and exactly the DAGs admit a topological order.

Practise directed graphs, in-degree & out-degree free → All Graphs subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Sum degrees separatelyΣ in-deg(v) = Σ out-deg(v) = |E|. Each edge contributes one to each sum.
Test strong connectivityA DFS from a vertex must reach everything, and the same must hold in the reversed graph. Kosaraju’s algorithm generalises this to find all strongly connected components.
Detect cycles for the DAG testA DFS finding a back edge means a directed cycle. Equivalently, a failed topological sort.
Identify sources and sinksA source has in-degree 0, a sink out-degree 0. Every finite DAG has at least one of each.

Worked example

A digraph on {1,2,3} has edges 1→2, 2→3, 3→1. Is it strongly connected? Is it a DAG?

From 1 we reach 2, then 3, then back to 1 — all vertices reachable from 1.
By symmetry of the cycle, every vertex reaches every other.
So it is strongly connected.
But 1→2→3→1 is a directed cycle, so it is not acyclic.

Answer. Strongly connected but not a DAG — indeed a strongly connected digraph on more than one vertex always contains a cycle.

Where marks get dropped

These are the specific errors that cost credit on directed graphs, in-degree & out-degree questions — QED's rubric penalises each of them separately.

Using the handshake lemma unmodified. In a digraph each degree sum is |E|, not 2|E|.
Confusing weak and strong connectivity. 1→2←3 is weakly connected but far from strongly connected.
Assuming a DAG has no undirected cycles. A DAG can look cyclic when directions are ignored — the diamond is the standard example.

Practise this until it is automatic

Unlimited fresh questions

QED generates new directed graphs, in-degree & out-degree problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.

Directed graphs, in-degree & out-degree — frequently asked questions

What is a strongly connected component?

A maximal set of vertices all mutually reachable. Contracting each SCC to a single vertex always yields a DAG — the condensation.

Which digraphs have topological orders?

Exactly the DAGs. A directed cycle makes an ordering impossible, and acyclicity guarantees one exists.

Is Euler’s criterion different for digraphs?

Yes: a connected digraph has an Euler circuit iff every vertex has equal in-degree and out-degree.

The rest of Graphs

Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make directed graphs, in-degree & out-degree exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →