Graph Theory: exercises

Practice (40)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

1. The questions in this exercise pertain to the graph \(\bfG\) shown in .

   1. What is the degree of vertex \(8\)?

   2. What is the degree of vertex \(10\)?

   3. How many vertices of degree \(2\) are there in \(\bfG\)? List them.

   4. Find a cycle of length \(8\) in \(\bfG\).

   5. What is the length of a shortest path from \(3\) to \(4\)?

   6. What is the length of a shortest path from \(8\) to \(7\)?

   7. Find a path of length \(5\) from vertex \(4\) to vertex \(6\).

2. Draw a graph with \(8\) vertices, all of odd degree, that does not contain a path of length \(3\) or explain why such a graph does not exist.

3. Draw a graph with \(6\) vertices having degrees \(5\), \(4\), \(4\), \(2\), \(1\), and \(1\) or explain why such a graph does not exist.

4. For the next Olympic Winter Games, the organizers wish to expand the number of teams competing in curling. They wish to have \(14\) teams enter, divided into two pools of seven teams each. Right now, they're thinking of requiring that in preliminary play each team will play seven games against distinct opponents. Five of the opponents will come from their own pool and two of the opponents will come from the other pool. They're having trouble setting up such a schedule, so they've come to you. By using an appropriate graph-theoretic model, either argue that they cannot use their current plan or devise a way for them to do so.

   Odhalte odpověď

   We attempt to construct a graph in which the vertices correspond to teams and there is an edge between two teams if and only if they play a game. To see why the organizers proposal is impossible, we consider just what the (sub)graph consisting of the teams in a single pool would look like. This graph would have seven vertices, and since each team would play five games against teams in the same pool, each vertex would have degree five. However, this would then require that the graph have an odd number (seven) of vertices of odd (five) degree, which we know is impossible. You could also say that the sum of the degrees of the vertices in this subgraph would be \(7\cdot 5 = 35\), which is not even as required by .

5. For this exercise, consider the graph \(\bfG\) in .

   1. Let \(V_1=\{g,j,c,h,e,f\}\) and \(E_1=\{ge,jg,ch,ef\}\). Is \((V_1,E_1)\) a subgraph of \(\bfG\)?

   2. Let \(V_2=\{g,j,c,h,e,f\}\) and \(E_2=\{ge,jg,ch,ef,cj\}\). Is \((V_2,E_2)\) a subgraph of \(\bfG\)?

   3. Let \(V_3=\{a,d,c,h,b\}\) and \(E_3=\{ch,ac,ad,bc\}\). Is \((V_3,E_3)\) an induced subgraph of \(\bfG\)?

   4. Draw the subgraph of \(\bfG\) induced by \(\{g,j,d,a,c,i\}\).

   5. Draw the subgraph of \(\bfG\) induced by \(\{c,h,f,i,j\}\).

   6. Draw a subgraph of \(\bfG\) having vertex set \(\{e,f,b,c,h,j\}\) that is not an induced subgraph.

   7. Draw a spanning subgraph of \(\bfG\) with exactly \(10\) edges.

6. Prove that every tree on \(n\) vertices has exactly \(n-1\) edges.

7. contains four graphs on six vertices. Determine which (if any) pairs of graphs are isomorphic. For pairs that are isomorphic, give an isomorphism between the two graphs. For pairs that are not isomorphic, explain why.

   Odhalte odpověď

   We first note that \(\mathbf{G}_{4}\) is the only graph of the four containing a vertex of degree 1. Therefore, this graph is not isomorphic to any of the other three. Notice next that in \(\mathbf{G}_{2}\), there are two vertices of degree \(3\): \(u_{3}\) and \(u_{6}\). These vertices are not adjacent in \(\mathbf{G}_{2}\). However, in \(\mathbf{G}_{1}\) and \(\mathbf{G}_{3}\), there are also two vertices of degree \(3\) and those vertices are adjacent in those graphs. This prevents \(\mathbf{G}_{2}\) from being isomorphic to either \(\mathbf{G}_{1}\) or \(\mathbf{G}_{3}\).

   The graphs \(\mathbf{G}_{1}\) and \(\mathbf{G}_{3}\) are isomorphic. There are two isomorphisms between them, one of which is given below: \[\begin{aligned}f(v_{1})\amp= w_{2} \\ f(v_{2})\amp= w_{3} \\ f(v_{3})\amp= w_{4} \\ f(v_{4})\amp= w_{1} \\ f(v_{5})\amp= w_{6} \\ f(v_{6})\amp= w_{5}\end{aligned}\]

8. Find an eulerian circuit in the graph \(\bfG\) in or explain why one does not exist.

9. Consider the graph \(\bfG\) in . Determine if the graph is eulerian. If it is, find an eulerian circuit. If it is not, explain why it is not. Determine if the graph is hamiltonian. If it is, find a hamiltonian cycle. If it is not, explain why it is not.

   Odhalte odpověď

   We first address hamiltonicity. Notice that because \(g\) and \(n\) both have degree \(2\), if there is a hamiltonian cycle, it must use the edges incident with \(g\) and \(n\). However, both of these vertices are adjacent to \(m\). Thus, \(m\) already has two edges in a hypothetical hamiltonian cycle, which means that there cannot be a hamiltonian cycle as no other vertices could be included.

   We now proceed to apply the algorithm to find an eulerian circuit. The algorithm finds an eulerian circuit without needing multiple phases, and that circuit is \((a,b,l,a,e,f,c,i,d,h,m,c,j,d,l,j,m,g,n,m,i,f,k,a)\).

10. Explain why the graph \(\bfG\) in does not have an eulerian circuit, but show that by adding a single edge, you can make it eulerian.

11. An eulerian trail is defined in the same manner as an eulerian circuit (see ) except that we drop the condition that \(x_0=x_t\). Prove that a graph has an eulerian trail if and only if it is connected and has at most two vertices of odd degree.

12. Alice and Bob are discussing a graph that has \(17\) vertices and \(129\) edges. Bob argues that the graph is hamiltonian, while Alice says that he's wrong. Without knowing anything more about the graph, must one of them be right? If so, who and why, and if not, why not?

13. Find the chromatic number of the graph \(\bfG\) in and a coloring using \(\chi(\bfG)\) colors.

14. Find the chromatic number of the graph \(\bfG\) in and a coloring using \(\chi(\bfG)\) colors.

    Odhalte odpověď

    Notice that the vertices \(\{f,b,g,l\}\) form a clique of size 4. Thus, the chromatic number of \(\mathbf{G}\) is at least 4. There are many proper colorings using four colors, so \(\chi(\mathbf{G}) = 4\). A complete and correct solution will show such a proper coloring.

15. A pharmaceutical manufacturer is building a new warehouse to store its supply of \(10\) chemicals it uses in production. However, some of the chemicals cannot be stored in the same room due to undesirable reactions that will occur. The matrix below has a \(1\) in position \((i,j)\) if and only if chemical \(i\) and chemical \(j\) cannot be stored in the same room. Develop an appropriate graph theoretic model and determine the smallest number of rooms into which they can divide their warehouse so that they can safely store all \(10\) chemicals in the warehouse. \[\begin{aligned}\end{aligned}\]

    Odhalte odpověď

    We can define a graph from this situation by letting the vertices be the chemicals. We place an edge between two vertices if and only if the corresponding chemicals cannot be stored in the same room, which means we place an edge if and only if there is a 1 in the matrix. A proper coloring of this graph corresponds to a storage plan, since we can safely place all chemicals with the same color in a single warehouse. The chromatic number of the graph is thus the minimum number of warehouses required. After drawing such a graph (labeling the vertices by the row/column number to which they correspond), we identify that \(\{1,2,4,5\}\) is a 4-clique in the graph. Thus, the chromatic number is at least 4. There are many proper 4-colorings, so the chromatic number is 4 and 4 is the minimum number of warehouses required. A complete and correct solution will show such a proper coloring.

16. A school is preparing the schedule of classes for the next academic year. They are concerned about scheduling calculus, physics, English, statistics, economics, chemistry, and German classes, planning to offer a single section of each one. Below are the lists of courses that each of six students must take in order to successfully graduate. Determine the smallest number of class periods that can be used to schedule these courses if each student can take at most one course per class period. Explain why fewer class periods cannot be used.

    Student	Courses
    1	Chemistry, Physics, Economics
    2	English, German, Statistics
    3	Statistics, Calculus, German
    4	Chemistry, Physics
    5	English, Chemistry
    6	Chemistry, Economics

    Odhalte odpověď

    We use a graph-theoretic model in which the vertices of our graph are the courses. We place an edge between two vertices/courses if and only if a student needs to take both of the courses, as then a proper coloring of the graph will ensure that no pair of courses that must both be taken by any student are scheduled at the same time. After constructing the graph, we see that there are multiple \(3\)-cliques (for example, chemistry, physics, and economics), so we know that at least three colors (class periods) are required. As an example of a proper 3-coloring, we could color physics, English, and calculus with color 1; color chemistry and German with color 2; and color economics and statistics with color 3. This shows that 3 is the minimum number of class periods required.

17. All trees with more than one vertex have the same chromatic number. What is it, and why?

    Odhalte odpověď

    By definition, a tree is a connected graph with no cycles. If \(\mathbf{T}\) is a tree, it therefore cannot contain any odd cycles since it has no cycles. Thus, we know that \(\mathbf{T}\) is bipartite. Since we have assumed the tree has at least two vertices, it has at least one edge. Therefore, we cannot use only one color. Thus, \(\chi(\mathbf{T}) = 2\).

18. Find a proper \((t+1)\)-coloring of the graph \(\bfG_{t+1}\) in Mycielski's proof of . This establishes that \(\chi(\bfG_{t+1})\leq t+1\).

19. How many vertices does the graph \(\bfG_4\) from the Kelly and Kelly proof of have?

20. Construct and draw the graph \(\bfG_5\) from Mycielski's proof of .

21. Find a recursive formula for the number of vertices \(n_t\) in the graph \(\bfG_t\) from the Kelly and Kelly proof of .

22. Let \(b_t\) be the number of vertices in the graph \(\bfG_t\) from the Mycielski's proof of . Find a recursive formula for \(b_t\).

23. The girth of a graph \(\bfG\) is the number of vertices in a shortest cycle of \(\bfG\). Find the girth of the graph \(\bfG_t\) in the Kelly and Kelly proof of and prove that your answer is correct. As a challenge, see if you can modify the construction of \(\bfG_t\) to increase the girth. If so, how far are you able to increase it?

24. Use the First Fit algorithm to color the graph in using the two different orderings of the vertex set shown there.

25. Draw the interval graph corresponding to the intervals in .

26. Use the First Fit coloring algorithm to find the chromatic number of the interval graph whose interval representation is shown in as well as a proper coloring using as few colors as possible.

27. 1. From you know that choosing a bad ordering of the vertices of a graph can lead to the First Fit coloring algorithm producing a coloring that is far from optimal. However, you can use this algorithm to prove a bound on the chromatic number. Show that if every vertex of \(\bfG\) has degree at most \(D\), then \(\chi(\bfG)\leq D+1\).

    2. Give an example of a bipartite graph with \(D=1000\) to show that this bound need not be tight.

28. Is the graph in planar? If it is, find a drawing without edges crossings. If it is not give a reason why it is not.

    Odhalte odpověď

    The graph is planar. Answers will vary.

29. Is the graph in planar? If it is, find a drawing without edge crossings. If it is not give a reason why it is not.

    Odhalte odpověď

    This graph is not planar. It contains a subdivision of \(\mathbf{K}_{3,3}\). The vertices on one side of the \(\mathbf{K}_{3,3}\) are \(\{d,a,g\}\) and on the other side you have \(\{e,l,i\}\). These vertices form a \(\mathbf{C}_{6}\) in the given graph, so we just need paths or edges from \(d\) to \(l\), from \(a\) to \(i\), and from \(g\) to \(e\). We can use \((d,j,c,l)\), \((a,f,i)\), and \((g,k,h,e)\) to do this. (Note that since there are not five vertices of degree at least \(4\), there cannot be a \(\mathbf{K}_{5}\) subdivision.)

30. Find a planar drawing of the graph \(\bfK_5-e\), by which we mean the graph formed from the complete graph on \(5\) vertices by deleting any edge.

31. Exhibit a planar drawing of an eulerian planar graph with \(10\) vertices and \(21\) edges.

32. Show that every planar graph has a vertex that is incident to at most five edges.

33. Let \(\GVE\) be a graph with \(V=\{v_1,v_2,\dots,v_n\}\). Its degree sequence is the list of the degrees of its vertices, arranged in nonincreasing order. That is, the degree sequence of \(\mathbf{G}\) is \((\deg_\mathbf{G}(v_1),\deg_\mathbf{G}(v_2),\dots,\deg_\mathbf{G}(v_n))\) with the vertices arranged such that \(\deg_\mathbf{G}(v_1) \geq \deg_\mathbf{G}(v_2)\geq \cdots\geq \deg_\mathbf{G}(v_n)\). Below are five sequences of integers (along with \(n\), the number of integers in the sequence). Identify

    • onecannot be the degree sequence of any graph
    • twoplanar
    • onetree
    • oneeulerian
    • onehamiltonian

    Explain your answers. (Note that one sequence will get two labels from above.)

    1. \(n=10\): \((4,4,2,2,1,1,1,1,1,1)\)

    2. \(n=9\): \((8,8,8,6,4,4,4,4,4)\)

    3. \(n=7\): \((5,4,4,3,2,1,0)\)

    4. \(n=10\): \((7,7,6,6,6,6,5,5,5,5)\)

    5. \(n=6\): \((5,4,3,2,2,2)\)

    Odhalte odpověď

    1. \(9\leq 3\cdot 10-6 = 24\)
    2. \(9\)\(3\cdot 9 -6 = 21\)\(9\)
    3. No graph with this degree sequence exists, since it would need to have three vertices of odd degree. Since three is odd, this would violate the First Theorem of Graph Theory.
    4. \(10/2 = 5\)\(29\)\(3\cdot 10-6=24\)\(10\)
    5. \(3\cdot 6-6 = 12\)\(6\)

34. Below are three sequences of length \(10\). One of the sequences cannot be the degree sequence (see ) of any graph. Identify it and say why. For each of the other two, say why (if you have enough information) a connected graph with that degree sequence

    • is definitely hamiltonian/cannot be hamiltonian;
    • is definitely eulerian/cannot be eulerian;
    • is definitely a tree/cannot be a tree; and
    • is definitely planar/cannot be planar.

    (If you do not have enough information to make a determination for a sequence without having specific graph(s) with that degree sequence, write not enough information for that property.)

    1. \((6,6,4,4,4,4,2,2,2,2)\)

    2. \((7,7,7,7,6,6,6,2,1,1)\)

    3. \((8,6,4,4,4,3,2,2,1,1)\)

35. For the two degree sequences in that correspond to graphs, there were some properties for which the degree sequence was not sufficient information to determine if the graph had that property. For each of those situations, see if you can draw both a graph that has the property and a graph that does not have the property.

36. Draw the \(16\) labeled trees on \(4\) vertices.

37. Determine \(\prufer(\bfT)\) for the tree \(\bfT\) in .

    Odhalte odpověď

    Applying the algorithm, we obtain \((1,4,6,9,4,9,1,4)\).

38. Determine \(\prufer(\bfT)\) for the tree \(\bfT\) in .

39. Determine \(\prufer(\bfT)\) for the tree \(\bfT\) .

    Odhalte odpověď

    Applying the algorithm, we find that the Prüfer code for this tree is \((9,3,9,5,9,4,5,14,1,6,5,1)\).

40. Construct the labeled tree \(\bfT\) with Prüfer code \(96113473\).

    Odhalte odpověď

    We are given the Prüfer code \(96113473\). This has length 8, so we know that the tree has \(10=8+2\) vertices. We construct the table that will allow us to identify the edges:

    Prüfer Code	Labels Remaining	Edge Added
    96113473	\(\{1,2,3,4,5,6,7,8,9,10\}\)	29
    6113473	\(\{1,3,4,5,6,7,8,9,10\}\)	56
    113473	\(\{1,3,4,6,7,8,9,10\}\)	61
    13473	\(\{1,3,4,7,8,9,10\}\)	81
    3473	\(\{1,3,4,7,9,10\}\)	13
    473	\(\{3,4,7,9,10\}\)	94
    73	\(\{3,4,7,10\}\)	47
    3	\(\{3,7,10\}\)	73
    empty string	\(\{3,10\}\)	103

Zkuste si vlastní.

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Více v Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs