Graph Concepts¶

In one sentence

A graph is a set of things (vertices) plus a set of connections between pairs of them (edges). Almost every "who is connected to whom" problem becomes easy once you can name its parts precisely.

1. Why graphs?¶

Example — 1829F · Forever Winter (5-Graph · A, rating 1300)

A snowflake graph is built from two integers \(x, y > 1\):

Start with one central vertex.
Connect \(x\) new vertices to the centre.
Connect \(y\) new vertices to each of those \(x\) vertices.

You are given the edges of a snowflake graph (vertex numbers are shuffled). Find \(x\) and \(y\).

Limits: \(t \le 1000\) test cases, \(n \le 200\), \(m \le 1000\).

Input          Output
3
21 20
21 20          5 3
5 20
... (18 more edges)
7 6
1 2            2 2
1 3
2 4
2 5
3 6
3 7
9 8
9 3            2 3
3 6
6 2
2 1
5 2
2 7
4 3
3 8

The second test case, drawn:

graph TD
  1((1 centre)) --- 2((2))
  1 --- 3((3))
  2 --- 4((4))
  2 --- 5((5))
  3 --- 6((6))
  3 --- 7((7))

The vertex numbers tell us nothing, so the only information is how many edges touch each vertex. That number is the vertex's degree, and it is enough:

kind of vertex	how many	degree
centre	\(1\)	\(x\)
middle	\(x\)	\(y + 1\) (the centre, plus \(y\) outer ones)
outer	\(x \cdot y\)	\(1\)

So the degree-\(1\) vertices (the leaves) number \(xy\), and all the others number \(x + 1\). Count both, and \(x\) and \(y\) follow. The worked solution is in §4.

This page defines degree, leaf, and the other words graph problems use. Graph Storage & Traversal shows how to walk a graph in code.

2. Definitions¶

2.1 Graph, vertex, edge¶

A graph is written \(G = (V, E)\):

\(V\) is the set of vertices (also called nodes). In problems they are usually numbered \(1..n\), so \(n = |V|\).
\(E\) is the set of edges. Each edge connects two vertices, and \(m = |E|\).

kind	edge written as	meaning	picture
undirected	\((u, v)\), the same as \((v, u)\)	a two-way road	`u --- v`
directed	\(u \to v\)	a one-way street from \(u\) to \(v\)	`u --> v`
weighted	\((u, v, w)\)	the edge has a length or cost \(w\)	`u --w-- v`

graph LR
  a1((1)) ---|undirected| a2((2))
  b1((1)) -->|directed| b2((2))
  c1((1)) ---|"weighted: 5"| c2((2))

Two vertices joined by an edge are adjacent (they are neighbours).

Self-loops and multi-edges

A self-loop is an edge \((v, v)\). Multi-edges are two or more edges between the same pair of vertices. A graph with neither is a simple graph. Forever Winter promises a simple graph ("no multiple edges and self-loops"), but many problems do not. Read the statement.

2.2 Degree¶

The degree \(\deg(v)\) of a vertex is the number of edges touching it. A self-loop counts twice.

In a directed graph we split it: out-degree \(\deg^+(v)\) counts arrows leaving \(v\), and in-degree \(\deg^-(v)\) counts arrows entering \(v\).

Handshake lemma. In every undirected graph,

\[ \sum_{v \in V} \deg(v) = 2m . \]

Proof. Every edge \((u, v)\) adds \(1\) to \(\deg(u)\) and \(1\) to \(\deg(v)\), which is \(2\) in total. Adding over all \(m\) edges gives \(2m\). \(\blacksquare\)

Corollary. The number of vertices with odd degree is even. Removing the even degrees from the left side leaves an even number, and a sum of odd numbers is even only when there are an even number of them.

For directed graphs the same counting gives \(\sum \deg^+(v) = \sum \deg^-(v) = m\).

The handshake lemma on a snowflake

A snowflake has \(m = x + xy\) edges (\(x\) to the centre, \(xy\) to the outer vertices). Add up the degrees from the table in §1:

\[ x \;+\; x(y + 1) \;+\; xy \cdot 1 \;=\; 2x + 2xy \;=\; 2m . \checkmark \]

For the second sample (\(x = y = 2\)): degrees \(2, 3, 3, 1, 1, 1, 1\) sum to \(12 = 2 \cdot 6\).

2.3 Path, cycle, connectivity¶

A path is a sequence of vertices \(v_0, v_1, \dots, v_k\) where consecutive vertices are adjacent and no vertex repeats. Its length is \(k\), the number of edges.
A cycle is a path that returns to its start: \(v_0 = v_k\), with \(k \ge 3\) in a simple graph and no other repeats.
\(u\) and \(v\) are connected if some path goes from \(u\) to \(v\).
A graph is connected if every pair of vertices is connected.
A connected component is a maximal group of vertices that are all connected to each other. "Maximal" means that adding any other vertex would break this.

Every vertex belongs to exactly one component. So the components split \(V\) into disjoint groups, which is exactly what DSU keeps track of.

2.4 Trees¶

A tree is a connected graph with no cycles. A snowflake is a tree. For a graph with \(n\) vertices, these three statements are equivalent: if one is true, all are.

\(G\) is connected and has no cycle.
\(G\) is connected and has exactly \(n - 1\) edges.
Between any two vertices there is exactly one path.

Check on the snowflake: \(n = 1 + x + xy\) and \(m = x + xy = n - 1\). ✓

Why a tree has \(n - 1\) edges. First, every tree with \(n \ge 2\) vertices has a leaf (degree \(1\)). Take the longest path in the tree. Its last vertex cannot have another neighbour further along the path, because the path is longest. It cannot have a neighbour earlier on the path either, because that would make a cycle. So its degree is \(1\).

Now remove a leaf and its one edge. What remains is still connected and still has no cycle, so it is a tree with \(n - 1\) vertices. Repeat until one vertex is left. Each step removed exactly one edge, and there were \(n - 1\) steps, so there were \(n - 1\) edges. \(\blacksquare\)

Words for a rooted tree (pick one vertex as the root):

graph TD
  1((1 root)) --- 2((2))
  1 --- 3((3))
  3 --- 4((4 leaf))
  3 --- 5((5 leaf))
  2 --- 6((6 leaf))

word	meaning	example above
parent / child	the neighbour one step closer to / further from the root	\(3\) is the parent of \(4\) and \(5\)
leaf	a vertex with no children	\(4, 5, 6\)
depth	number of edges from the root	depth of \(4\) is \(2\)
subtree of \(v\)	\(v\) and everything below it	subtree of \(3\) is \(\{3, 4, 5\}\)

2.5 One more edge: unicyclic graphs¶

A connected graph with \(n\) vertices and \(n - 1\) edges is a tree. Add one more edge \((u, v)\): there was already exactly one path from \(u\) to \(v\), and together with the new edge it forms exactly one cycle.

So a connected graph with \(n\) vertices and \(n\) edges has exactly one cycle. It looks like a cycle with trees hanging off its vertices:

graph LR
  1((1)) --- 2((2))
  2 --- 3((3))
  3 --- 4((4))
  4 --- 1
  2 --- 5((5))
  5 --- 6((6))
  4 --- 7((7))

This shape appears in 1873H · Mad City.

3. Lesson notes — March 22¶

Recap¶

Today we continued working on graph problems.

The most important part of graph theory is usually the modeling. If you can clearly figure out how to construct the graph and what each node or edge represents, then many problems become much more manageable.

Another important point is that graph problems do not always require us to build the graph in a very strict way and then immediately write a search. Sometimes, after observing the degree of each node and the special properties in the input, it is helpful to make a bold assumption or think about the problem from the opposite direction.

For example, if a problem is stated on a rooted tree and asks us to think from the root downward, it may actually be easier to start from the leaves and reason backward.

We also learned a new graph concept today: the diameter.

In a connected graph, the diameter is the length of the path between the two farthest nodes. A common way to find it is:

Start from any node and run one search to find a farthest node \(u\).
Start from \(u\) and run another search to find one of the farthest nodes \(v\).
The path from \(u\) to \(v\) is a diameter of the graph.

Concepts¶

Connected Graph¶

A graph is called connected if every pair of nodes has a path between them. In other words, starting from any node, we can eventually reach every other node in the graph.

Degree¶

The degree of a node is the number of edges connected to it.

In a tree:

A node with degree \(1\) is usually a leaf, unless the tree has only one node.
Large degrees often mean that the node connects many branches, so degree can give us useful structural information.

Tree¶

A tree is a connected graph with no cycles.

Useful properties of a tree:

If a tree has \(N\) nodes, then it has exactly \(N - 1\) edges.
There is exactly one simple path between any two nodes.
Many tree problems can be solved with DFS, BFS, or by reasoning from leaves upward.

Leaf¶

A leaf is a node with degree \(1\) in a tree.

Leaves are often good starting points for observation, especially when the problem statement is written from the root's perspective but the structure is easier to understand from the outside inward.

Diameter¶

The diameter of a connected graph is the length of the path between two farthest nodes.

For a tree, a standard way to find the diameter is:

Start from any node and run DFS or BFS to find a farthest node \(u\).
Start from \(u\) and run DFS or BFS again to find a farthest node \(v\).
The path from \(u\) to \(v\) is a diameter.

This method is very common and should be remembered.

4. Worked solution — Forever Winter¶

Count degrees. Leaves have degree \(1\), and there are \(xy\) of them. The other \(x + 1\) vertices are the centre and the middle ring. So \(x = (\text{non-leaves}) - 1\) and \(y = \text{leaves} / x\).

import sys

input = sys.stdin.readline


def solve():
    n, m = map(int, input().split())

    deg = [0] * (n + 1)
    for _ in range(m):
        u, v = map(int, input().split())
        deg[u] += 1
        deg[v] += 1

    leaves = 0
    others = 0
    for v in range(1, n + 1):
        if deg[v] == 1:
            leaves += 1
        else:
            others += 1

    x = others - 1
    y = leaves // x
    print(x, y)


t = int(input())
for _ in range(t):
    solve()

Check the samples:

test	\(n\)	leaves	others	\(x = \text{others} - 1\)	\(y = \text{leaves} / x\)
1	21	15	6	5	3
2	7	4	3	2	2
3	9	6	3	2	3

Why \(x, y > 1\) matters

If \(y\) could be \(0\), the middle vertices would be leaves too, and counting degree-1 vertices would mix them up. The statement guarantees \(x, y > 1\), so the centre has degree \(\ge 2\) and the middle vertices have degree \(\ge 3\): only outer vertices have degree \(1\).

5. Common mistakes¶

Adding an undirected edge only once

An undirected edge \((u, v)\) adds to the degree of both \(u\) and \(v\), and must appear in the adjacency lists of both (see the lesson notes on the next page).

\"\(m = n - 1\), so it is a tree\"

Not without connectivity. \(4\) vertices with edges \(1\)–\(2\), \(2\)–\(3\), \(3\)–\(1\) has \(3 = n - 1\) edges, but vertex \(4\) is isolated and there is a cycle.

0-indexed vs 1-indexed vertices

Inputs almost always use \(1..n\). Allocate n + 1 slots, or subtract \(1\) when reading, but pick one and stay consistent.

Leaf in a rooted vs unrooted tree

In an unrooted tree a leaf has degree \(1\). In a rooted tree the root can have degree \(1\) and still not be called a leaf. 1593E · Gardener and Tree even calls a single vertex a leaf. Read the problem's definition.

6. Practice¶

Problem	Set	Rating	Concept used
1829F · Forever Winter	5-Graph · A	1300	degrees (this page)
1675D · Vertical Paths	5-Graph · F	1300	parent / child / leaf in a rooted tree
1593E · Gardener and Tree	5-Graph · H	1600	peeling leaves layer by layer
1833E · Round Dance	5-Graph · C	1600	components where every degree is ≤ 2: cycles vs. chains
1873H · Mad City	5-Graph · I	1700	\(n\) vertices, \(n\) edges: exactly one cycle

Credits & licenses

Definitions and the handshake lemma (§2.1–2.3): adapted and translated from OI Wiki — Graph Concepts by the OI Wiki contributors, licensed CC BY-SA 4.0. Wording simplified; examples and pictures are ours.
Section structure follows USACO Guide — Introduction to Graphs by Darren Yao and Benjamin Qi, licensed CC BY-NC-SA 4.0.
Everything else (the snowflake analysis, the tree proof, the unicyclic argument, the code, mistakes) is ours. §3 is our lesson recap.