# Concept derivation guides

299 concept teaching guides, separate from the 36,000 individual question derivations.

[Search all questions & derivations →](/en/explore/)

1 5 results · Page 1 of 1



Concept guide



## [Finite simple undirected graphs: neighbours, degrees and the handshake formula](/en/derivations/derivation-mko-graph-01/?from=%2Fen%2Fderivations%2F%3Fq%3Dmko-graph)

Let V={1,2,3,4,5}, with edges entered as a list of endpoint pairs: (1,2), (2,1), (2,3), (3,4), (2,4), (4,2), each entry denoting an undirected edge. Normalize the input to the edge set E, find the neighbour set N(v) and degree deg(v) of every vertex, check that the degree sum equals 2|E|, and prove the handshake formula Σ_{v∈V} deg(v)=2|E| for every finite simple undirected graph.

Finite simple undirected graphs

derivation-mko-graph-01



Concept guide



## [Graph isomorphism: checking bijectivity and both directions of adjacency preservation from a complete mapping table](/en/derivations/derivation-mko-graph-isomorphism-01/?from=%2Fen%2Fderivations%2F%3Fq%3Dmko-graph)

G has vertices 1, 2, 3, 4 and edges {1,2}, {2,3}, {3,4}, {1,4}; H has vertices a, b, c, d and edges {a,c}, {b,c}, {b,d}, {a,d}. Prove that f: 1↦a, 2↦c, 3↦b, 4↦d is a graph isomorphism G→H; show that the bijection g: 1↦a, 2↦b, 3↦c, 4↦d is not an isomorphism; and prove that the path P (edges {1,2}, {2,3}, {3,4}) is not isomorphic to H, even though f sends every edge of P to an edge of H.

Graph isomorphism

derivation-mko-graph-isomorphism-01



Concept guide



## [Graph walks and simple paths: pair-by-pair checks, length and the difference from trails](/en/derivations/derivation-mko-graph-walk-simple-path-01/?from=%2Fen%2Fderivations%2F%3Fq%3Dmko-graph)

Finite undirected loop-free simple graph G: V={0,1,2,3,4}, E={{0,1},{1,2},{2,3},{0,3},{1,3},{3,4}}. For the vertex sequences W₁=(0,1,2,3,4), W₂=(0,1,3,1,2), W₃=(0,2,3), W₄=(2,3,0,1,3,4), W₅=(4) and W₆=(1,1), decide whether each is a walk, its length, and whether it is a simple path; also prove that a simple path repeats no edge and that in this graph a simple path has length at most 4.

Graph walks and simple paths

derivation-mko-graph-walk-simple-path-01



Concept guide



## [A complete coloring and a nonoptimal greedy trace](/en/derivations/derivation-mko-graph-coloring-01/?from=%2Fen%2Fderivations%2F%3Fq%3Dmko-graph)

Audit a proper coloring edgewise and show an upper bound need not be optimal.

Graph coloring

derivation-mko-graph-coloring-01



Concept guide



## [Maximal versus maximum in P4](/en/derivations/derivation-mko-graph-matching-01/?from=%2Fen%2Fderivations%2F%3Fq%3Dmko-graph)

Audit selected edges and endpoints, then distinguish matching properties.

Graph matching

derivation-mko-graph-matching-01





1 5 results · Page 1 of 1