University Discrete Mathematics — Graphs and Trees Worksheet

12 of the 14 questions

Each question targets one named concept from the sheet. Read them here, or print the PDF — it has working space under each one. 12 of the 14 questions are printed below. The other 2 are built on a diagram or a table of values that does not translate to the page, so they are in the free PDF — marked below where they would have come.

1. Q1Graph Terminology and Special Graphs

   Throughout this worksheet, graph means a simple undirected graph $G=(V,E)$: no loops, and no two edges joining the same pair of vertices. The edge $\{x,y\}$ is written $xy$.

   Let $V=\{a,b,c,d,e,f,g,h\}$ and $E=\{ab,ac,bc,cd,de,df,ef,fg\}$.

   1. Give $\mathrm{deg}(v)$ for every vertex. Name the isolated vertex (degree $0$) and the pendant vertex (degree $1$).
   2. List the neighbours of $d$. How many edges does the subgraph induced by $\{c,d,e,f\}$ have (every edge of $G$ with both ends in that set)?
   3. The complement $\bar{G}$ has the same vertices, two distinct vertices being adjacent in $\bar{G}$ exactly when they are not adjacent in $G$. How many edges does $\bar{G}$ have?
2. Q2Graph Terminology and Special Graphs

   A graph is bipartite when its vertices can be split into two sets so that every edge joins a vertex of one set to a vertex of the other. For each graph below, give the number of vertices, the number of edges, and say whether it is bipartite, with a reason (a valid split, or why none exists).

   1. $K_6$, the complete graph on $6$ vertices.
   2. $C_7$, the cycle on $7$ vertices.
   3. $K_{3,5}$, the complete bipartite graph with parts of sizes $3$ and $5$.
   4. $P_6$, the path $v_1{v}_2\cdots v_6$ on $6$ vertices.
3. Q3The Handshake Theorem and Degree Sequences

   A graph has $8$ vertices and $11$ edges. Seven of its vertices have degrees $1,1,2,2,3,3,4$.

   1. Find the degree of the eighth vertex, naming the theorem you use.
   2. Explain why no graph has degrees $5,4,3,3,2,1,1$.
4. Q4The Handshake Theorem and Degree Sequences

   Decide whether each list is the degree sequence of a graph. If it is, give such a graph by listing its edges; if it is not, explain why.

   1. $3,3,3,3,2,2$
   2. $4,4,4,1,1$
   3. $5,3,2,2,2$
5. Q5Adjacency Matrices and Graph Isomorphism

   The graph $G$ on vertices $v_1,\dots ,v_5$ has adjacency matrix $A$, where $a_{ij}=1$ if $v_i{v}_j$ is an edge and $a_{ij}=0$ otherwise: $$A=\left[\begin{array}{ccccc}0& 1& 1& 0& 1\\ 1& 0& 1& 1& 0\\ 1& 1& 0& 1& 0\\ 0& 1& 1& 0& 1\\ 1& 0& 0& 1& 0\end{array}\right].$$

   1. List the edges of $G$ and the degree of each vertex.
   2. The $(i,j)$ entry of $A^2$ is $(A^2{)}_{ij}={\sum }_{k=1}^5{a}_{ik}{a}_{kj}$, the number of walks of length $2$ from $v_i$ to $v_j$. Compute $(A^2{)}_{14}$ and list the walks it counts.
   3. Explain why $(A^2{)}_{ii}=\mathrm{deg}(v_i)$ for every $i$.
6. Q6Paths, Cycles and Connectivity

   Let $G$ have vertex set $\{1,2,\dots ,9\}$ and edges $12,23,13,34,56,67,78,58$.

   1. Give the connected components of $G$ as sets of vertices. Is $G$ connected?
   2. Give a cycle of length $4$ in $G$.
   3. Find the distance $d(1,4)$ (the length of a shortest path) and a path that realises it.
   4. Give a walk of length $4$ from $2$ to $4$ that is not a path.
7. Q7Paths, Cycles and Connectivity

   A bridge of a graph is an edge whose deletion increases the number of connected components; a cut vertex is a vertex whose deletion, together with its edges, does so. The connected graph $G$ has vertices $a,\dots ,h$ and edges $$ab,bc,ca,cd,de,ef,fg,gd,fh.$$ Find every bridge and every cut vertex, with a reason for each.

8. Q8Euler and Hamilton Paths and Circuits

   This question is built around a diagram or a table of values. Open it in the PDF.

9. Q9Euler and Hamilton Paths and Circuits
   1. The graph $G$ has vertices $1,\dots ,7$ and edges $12,14,15,24,26,34,36,37,56,57$. Find a Hamilton circuit (a circuit visiting every vertex exactly once).
   2. The graph $H$ has vertices $a,b,c,d,e$ and edges $ab,bc,ca,cd,de,ec$ (two triangles sharing the vertex $c$). Show that $H$ has an Euler circuit but no Hamilton circuit.
10. Q10Shortest Paths with Dijkstra's Algorithm

    This question is built around a diagram or a table of values. Open it in the PDF.

11. Q11Shortest Paths with Dijkstra's Algorithm

    A cycling network joins six stations $P,Q,R,U,V,W$ by trails with these lengths, in kilometres: $$PQ=7,PR=3,QR=2,QU=4,RU=8,RV=9,UV=1,UW=3,VW=5.$$ Use Dijkstra's algorithm from $P$ to find the shortest distance from $P$ to every other station and the station just before it on a shortest route. Then give the shortest route from $P$ to $W$.

12. Q12Trees and Their Properties

    A tree is a connected graph with no cycle, and a leaf is a vertex of degree $1$. A tree has exactly two vertices of degree $4$, three of degree $3$, one of degree $2$, and every other vertex is a leaf. How many leaves does it have, and how many vertices?

13. Q13Planar Graphs and Euler's Formula

    Euler's formula: a connected graph drawn in the plane without crossings, with $v$ vertices, $e$ edges and $f$ faces (the unbounded outer face included), satisfies $v-e+f=2$.

    1. A connected planar graph has $10$ vertices, each of degree $3$. How many faces does any crossing-free drawing of it have?
    2. A connected graph drawn without crossings has $12$ edges and $8$ faces. How many vertices does it have?
14. Q14Synthesis — drawing on several topics in this unit

    The graph $K$ has vertices $1,\dots ,6$, grouped into the pairs $\{1,2\}$, $\{3,4\}$, $\{5,6\}$. Two distinct vertices are adjacent exactly when they are not in the same pair.

    1. Give the degree of every vertex and use the handshake theorem to find the number of edges.
    2. Does $K$ have an Euler circuit? If so, give one.
    3. Give a Hamilton circuit of $K$.
    4. $K$ can be drawn without crossings. How many faces does such a drawing have?

The 9 challenge problems for this topic are a separate, paid sheet and are not reproduced here.

How to do every concept on this sheet

This is the part worksheet sites usually leave out. Below is the actual reasoning behind each group of questions — not a full solution set, the decisions that get you to one. Read it before you start, or after you get stuck.

The vocabulary, and the fact that it is all definitions

Q1 fixes the convention for the whole set: graph means a simple undirected graph G = (V, E), with no loops and no repeated edge, and the edge {x, y} is written xy. Everything the question asks — deg(v) for each vertex, the isolated vertex, the pendant vertex, the neighbours of one vertex, the edges of an induced subgraph, the edges of the complement — is a definition applied once. There is no technique here to learn and no shortcut to take; the work is being systematic enough that nothing is missed.

Special graphs, and deciding bipartiteness

Q2 names four families — Kₙ, Cₙ, Kₘ,ₙ and Pₙ — and asks for the number of vertices, the number of edges, and a decision about bipartiteness with a reason. Learn each family as a sentence, and the vertex and edge counts follow from the sentence rather than from a drawing you have to make every time.

So the edge count of a complete graph is the number of pairs, the edge count of a complete bipartite graph is a product by the product rule, and a cycle and a path on the same number of vertices differ by exactly one edge. Write the general formula and then substitute; a formula written once is worth more on an exam than four separate counts.

The handshake theorem, and what it can rule out

Every edge contributes 1 to the degree of each of its two ends, so summing deg(v) over all vertices counts every edge exactly twice. That one sentence is the whole theorem, and it is the only tool Q3 needs.

Q3(a) gives the number of vertices, the number of edges, and all but one degree, and asks for the missing one — name the theorem as the question requires, write the equation with the unknown degree in it, and solve. Q3(b) turns the same equation into an impossibility argument: a list of degrees can only belong to a graph if its total is twice a whole number of edges, so look at the parity of the sum before anything else. Phrase the answer as an argument, not as a verdict: the sum would have to equal twice an integer, and the marks are for saying why it cannot.

Degree sequences: building one or ruling it out

Q4 gives three lists and asks, for each, whether some graph has exactly those degrees. The two answers are completely different kinds of work, and the question is really asking you to decide which kind each list needs.

Adjacency matrices, and what a power of one counts

Q5 gives a graph as a 5 by 5 matrix A, with a 1 wherever two vertices are joined and a 0 otherwise. Part (a) is translation in the easy direction: the edges are the positions of the 1s above the diagonal, and the degree of a vertex is the number of 1s in its row. Since the graph is undirected the matrix is symmetric, so reading only the upper half lists each edge once rather than twice.

Part (b) is the one idea in this sheet. The question supplies the entry of A² as a sum over k of a term in row i and a term in column j, so no linear algebra is needed and nothing has to be recalled: each term of that sum is 1 exactly when both vᵢvₖ and vₖvⱼ are edges, which is exactly one two-step walk from vᵢ to vⱼ through vₖ. Compute the sum term by term, and then list the walks as the question asks — the count and the list must agree, and that agreement is the check.

Walks, paths, components and distance

Q6 is a vocabulary question with four parts, and the vocabulary is the part that is marked. A walk may repeat vertices and edges; a path may not; a cycle is a closed path; the distance d(x, y) is the length of a shortest path, counted in edges and not in vertices; and a component is a maximal set of vertices reachable from one another.

For the distance in Q6(c), a claimed shortest path needs two things: the path itself, and the reason nothing shorter exists. On a graph this size the reason is a short check — every walk of one or two edges from the starting vertex is easy to list, so say that none of them reaches the target. Q6(d) asks for a walk that is not a path, which is the definition tested from the other side: repeat a vertex or an edge on purpose, and count the edges rather than the vertices so the required length comes out right.

Bridges and cut vertices

Q7 defines both terms inside the question — a bridge is an edge whose removal increases the number of components, a cut vertex is a vertex whose removal, with its edges, does the same — and asks for every one of each, with a reason for each. The word every is what makes the question hard: a correct list is only half of it, because the other half is knowing that nothing was missed.

Euler and Hamilton: a test that exists, and one that does not

Q8 works on a drawn graph with six vertices and asks first for every degree and then whether an Euler circuit or an Euler path exists, justified by those degrees, with one written out if it does. An Euler circuit or path uses every edge exactly once, and the criterion is a parity count, a direct descendant of the handshake theorem: each visit to a vertex consumes two edges at it, one in and one out, except at the two ends of an open walk.

So the order of work in Q8 is fixed: degrees first, then count the odd ones, then decide, then construct if the count allows it. When you construct, start at an odd-degree vertex if there are two — an Euler path has to — and cross each edge off the list as you use it, so that the finished walk can be checked against the edge count in one line.

Q9(b) puts the two ideas on one small graph, made of two triangles sharing a vertex, and asks you to show the Euler side by the degree criterion and the Hamilton side by an argument. The second half is the interesting one: an impossibility claim about Hamilton circuits cannot be made by failing to find one, so it has to rest on a structural feature — a cut vertex has to be passed through more than once to get from one side of the graph to the other, and a Hamilton circuit is allowed to visit it only once. Write that as a proof, naming the vertex and the two sides.

Dijkstra's algorithm, run as a table

Q10 and Q11 are the same algorithm on two weighted networks — a courier's depots with travel times in minutes, and a cycling network with trail lengths in kilometres. Both give every edge weight in the question, both ask you to run the algorithm from a named starting vertex, and both want the working, not just the route. Q10 asks for the order in which vertices become permanent together with their labels; Q11 asks for a distance to every vertex and the vertex just before it on a shortest route.

Trees

A tree is a connected graph with no cycle, and a leaf is a vertex of degree 1. Q12 lists how many vertices a tree has of degree 4, of degree 3 and of degree 2, says every other vertex is a leaf, and asks for the number of leaves and the number of vertices.

It is worth knowing why a tree has one edge fewer than it has vertices, because the reason is the argument the course has been building towards all term: it is proved by induction on the number of vertices, with a leaf removed at the inductive step to reach a smaller tree. Q12 does not ask for that proof, but treating the fact as a formula to memorise rather than a theorem you could restate is what makes the next such question unapproachable.

Planar graphs and Euler's formula

Q13 quotes the formula it needs: a connected graph drawn in the plane with no crossings, with v vertices, e edges and f faces, satisfies v − e + f = 2. Both parts are the formula plus one other relation, and the skill is noticing which relation the part supplies.

Part (a) gives the number of vertices and the degree of each of them, and no edge count — so the handshake theorem supplies e before the formula can be used, which is the link the question is testing. Part (b) gives e and f directly, so the formula is rearranged for v in one line. In both, write the formula, list the quantities you know beside it, and only then substitute.

The synthesis question

Q14 defines a graph on six vertices by a rule rather than an edge list — the vertices come in three pairs, and two distinct vertices are joined exactly when they are not in the same pair — and then walks through four of this set's topics on that one graph. Translate the rule into a drawing or an edge list first; every part afterwards is easier on a picture than on the sentence.

Part (a) is Q3: read off the degree of a vertex from the rule, note that the rule treats all six alike, and use the handshake theorem to get the edge count rather than counting edges one at a time. Part (b) is Q8: the parity of those degrees decides the Euler question before any route is attempted, and only then is a circuit written out. Part (c) is Q9: search for a Hamilton circuit, and verify it by listing consecutive pairs against the rule. Part (d) is Q13: with v from the definition and e from part (a), Euler's formula gives the face count of any crossing-free drawing — and if your own drawing has crossings, that does not contradict the answer, since the question grants that a drawing without them exists.

Preview all 8 pages

Click any page to open the full PDF.

Getting the most out of it

Draw it, then never trust the drawing

A drawing is how you find a route, a cycle or a split; it is not why the answer is right. Every claim on this sheet is settled against the edge list or the definition — a degree recounted from the list, a Hamilton circuit checked pair by pair, a bridge justified by the components that remain. Two vertices that look close on a page are the commonest source of a wrong answer.

Count with the handshake theorem before you count edges

It appears in four different disguises on this sheet — a missing degree, an impossible list, an edge count from a regular graph, and the parity test for an Euler circuit. Whenever a question mentions degrees and edges in the same breath, write the sum equation down first.

Know which questions have a test and which need a search

Euler, bipartiteness and planarity all come with a criterion you can apply. Hamilton circuits do not. Recognising which kind of question you are in decides whether you should be computing or searching, and stops you hunting for a criterion that does not exist.

For an impossibility, name the obstruction

"I could not find one" is never an answer. A negative claim on this sheet rests on a parity, a ceiling, an odd cycle or a cut vertex — a fixed feature that rules out every attempt at once. Write the feature down first and the argument follows from it.

Keep the algorithm's table

Dijkstra's algorithm produces an order, a set of labels and a predecessor for each vertex, and different questions ask for different pieces of it. Keeping all three columns as you go means one run answers whatever is asked, instead of a second run done under exam pressure.

Common questions