Maths WorkshopMaths problems with full solutions

Graph theory

66 problems · Graph terminology, trees, paths, connectivity and planar graphs.

Search problems Level

Ex.237Basic graph terminology

#graph #vertices #edges #degree

Ex.238The complete graph $K_n$

#complete graph #edges #degree

Ex.239Parity of odd-degree vertices

#parity #degree #handshake

Ex.240The handshake lemma

#handshake lemma #degree sum #parity

Ex.340The handshake lemma

#graphs #parity

Ex.469The complement of a graph

#complement #graph #edges

Ex.470Connected components

#connectivity #connected components

Ex.471Paths and cycles

#path #cycle #walk

Ex.472Summary of graph theory

#summary #graph theory

#tree #connected acyclic #edges

Ex.474Leaves of a tree

#tree #leaves #degree

Ex.636How many colours does a graph with m edges need?

#graph colouring #chromatic number #extremal

Ex.957BFS and DFS

#BFS #DFS #traversal

Ex.958Bipartite graphs

#bipartite #2-coloring #odd cycle

Ex.959Cliques and independent sets

#clique #independent set #complement

Ex.960A graph with a unique degree sequence

#degree sequence #unique #graph

Ex.961Hamiltonian cycles (example)

#Hamiltonian #cycle #NP-hard

Ex.962Graph isomorphism

#isomorphism #bijection #invariant

Ex.963Matchings

#matching #bipartite #Hall

Ex.964Euler's formula application

#Euler formula #planar #faces

Ex.965Spanning trees

#spanning tree #subgraph #connectivity

Ex.966Characterizations of trees

#tree #characterization #connected

Ex.967Diameter of a tree

#tree #diameter #BFS

Ex.968Trees as minors

#tree #minor #contraction

Ex.1236Every tournament has a Hamiltonian path

#induction #tournaments #graphs #Hamiltonian path

Ex.1239A tree has at least as many leaves as its maximum degree

#trees #graphs #handshake lemma #degrees

Ex.1245Splitting a parliament into two houses

#monovariant #graphs #extremal #process

Ex.1248A graph is bipartite exactly when it has no odd cycle

#graph theory #bipartite graphs #colouring #cycles

Ex.1249When can a graph be drawn without lifting the pen?

#Euler circuit #graph theory #degrees #extremal trail

Ex.1306A cut containing at least half of the edges

#probabilistic method #expectation #graph theory #local improvement

Ex.1310Drawing K₈ without lifting the pen

#Euler trail #graph theory #degrees #construction

Ex.1681Planar bipartite bound

#bipartite #planar #edge bound

Ex.1682Chromatic number

#chromatic number #coloring #clique

Ex.1683Graphical degree sequences

#degree sequence #graphical #Erdős–Gallai

Ex.1684Dijkstra's algorithm

#Dijkstra #shortest path #weighted graph

Ex.1685Eulerian circuits

#Eulerian #Euler circuit #degree

Ex.1686The four-color theorem (statement)

#four-color #planar #chromatic

Ex.1687Hall's marriage theorem (statement)

#Hall #marriage #matching

Ex.1688$K_{3,3}$ is not planar

#bipartite #planarity #K33

Ex.1689Kőnig's theorem

#Kőnig #bipartite #matching #vertex cover

Ex.1690Kruskal's algorithm

#Kruskal #MST #greedy

Ex.1691Minimum degree and connectivity

#minimum degree #connectivity #edge connectivity

Ex.1692Moore bound

#Moore bound #diameter #degree

Ex.1693NP-hard problems in graphs

#NP-hard #Hamiltonian #coloring

Ex.1694Planar graphs and Euler's formula

#planar #Euler formula #faces

Ex.1695Prim's algorithm

#Prim #MST #greedy

Ex.1696Prüfer sequences

#Prüfer #bijection #labeled trees

Ex.1697Ramsey numbers

#Ramsey #R(3 #3) #coloring

Ex.1698Cayley's formula

#Cayley #labeled trees #count

Ex.1938Triangle-free graphs have at most n²/4 edges (Mantel)

#double counting #graphs #Cauchy–Schwarz #extremal graph theory

Ex.1940Graphs with no 4-cycle

#extremal graph theory #double counting #convexity #cycles

Ex.1941Hall's marriage theorem and regular bipartite graphs

#Hall's theorem #matchings #bipartite graphs #induction

Ex.1973Erdős's lower bound for Ramsey numbers

#probabilistic method #Ramsey theory #expectation

Ex.1974Hall's marriage theorem and a deck of cards

#Hall's theorem #matchings #bipartite graphs #induction

Ex.1978Turán's theorem

#graph theory #extremal #induction #Turán

Ex.2136Edge coloring (Vizing)

#Vizing #edge coloring #chromatic index

Ex.2137Erdős–Gallai theorem (statement)

#Erdős-Gallai #degree sequence #graphical

Ex.2138Erdős–Gyárfás conjecture (statement)

#Erdős-Gyárfás #conjecture #cycles

Ex.2139Expander graphs (statement)

#expander #spectral gap #connectivity

Ex.2140The four-color theorem proof (history)

#four-color #history #proof

Ex.2141Kuratowski's theorem (statement)

#Kuratowski #planarity #minors

Ex.2142Graph minors

#minor #Robertson-Seymour #structure

Ex.2143Perfect graphs

#perfect graph #clique #chromatic

Ex.2144Spectral graph theory (statement)

#spectral graph #eigenvalues #adjacency

Ex.2145Szemerédi's regularity lemma (statement)

#Szemerédi #regularity #dense graphs

Ex.2146Turán's theorem

#Turán #extremal #clique