9.1 Complete Graphs

Basic Skills

1. What is the defining property of a complete graph, and how does it differ from other types of graphs?
2. How many edges are there in a complete graph with 7 vertices? Show your calculation.
3. Sketch a complete graph with 6 vertices. Label the vertices and all edges.
4. Given a graph with 8 vertices and 16 edges, is it a complete graph? Justify your answer.
5. In a peer-to-peer network of 9 devices, each device must be directly connected to every other device. How many total connections are needed? What type of graph models this scenario?

Applications

6. A company wants to set up a fully connected peer-to-peer network with 8 servers. How many direct connections are required to ensure every server can communicate with every other server?
7. In a small social media platform, every user follows every other user. If there are 10 users, how many total follow relationships exist? What type of graph models this scenario?
8. A conference organizer wants every speaker to meet every other speaker for a one-on-one session. If there are 6 speakers, how many meetings must be scheduled?
9. A distributed system requires that each node synchronize data with every other node. If there are 12 nodes, how many synchronization links are needed?
10. In a classroom, each student is paired with every other student for a group project. If there are 7 students, how many unique pairs of students are there?

Challenge Problems

11. Prove that the number of edges in a complete graph with n vertices is given by the formula [latex]\frac{n(n-1)}{2}[/latex]. Use mathematical reasoning or induction.
12. A complete graph has 45 edges. How many vertices does it have? Show your work and explain how you derived the answer.
13. Compare the edge density of a complete graph with 10 vertices to a graph with 10 vertices and only 20 edges. What does this tell you about connectivity?
14. A team of 12 engineers needs to collaborate, but due to bandwidth limits, each engineer can only maintain 6 direct connections. Can a complete graph model this scenario? Why or why not?
15. In a complete graph with 7 vertices, one edge is removed. Is the resulting graph still connected? How many edges must be removed before the graph becomes disconnected?

9.2 Connected Graphs

Basic Skills

16. What does it mean for a graph to be connected? How is this different from a disconnected graph?
17. Given a graph with 5 vertices and the following edges: {(1, 2), (2, 3), (3, 4), (4, 5)}, is the graph connected? Explain your reasoning.
18. A graph has 6 vertices and only 2 edges: (1, 2) and (3, 4). Is this graph connected? Why or why not?
19. Sketch a simple connected graph with 4 vertices. Then sketch a disconnected graph with the same number of vertices.
20. What is a “component” in the context of a disconnected graph? How many components does a graph with two isolated subgraphs have?

Applications

21. A company’s internal network is modelled as a graph. If one server becomes disconnected from the rest, what does this imply about the graph’s connectivity? How might this affect data flow?
22. In a social media platform, users are represented as vertices and friendships as edges. What does it mean if the graph is disconnected? How could this impact recommendation algorithms?
23. A delivery routing system is modelled as a graph where intersections are vertices and roads are edges. Why is it important for the graph to be connected? What happens if a road closure causes disconnection?
24. In a project management tool, tasks are represented as vertices and dependencies as edges. What does a disconnected graph indicate about the workflow? How can this be resolved?
25. A city’s emergency communication system is modelled as a graph. If the graph is not connected, what risks does this pose during a crisis? How can graph connectivity be used to improve resilience?

Challenge Problems

26. Prove that a connected graph with [latex]n[/latex] vertices must have at least [latex]n - 1[/latex] edges. What kind of graph has exactly [latex]n - 1[/latex] edges?
27. A connected graph has 10 vertices and 15 edges. What is the minimum number of edges that must be removed to make the graph disconnected? Justify your answer.
28. A graph has 12 vertices and 3 disconnected components. If one component has 5 vertices and another has 4, how many vertices are in the third component? How many edges are needed to make the graph connected?
29. A connected graph has 7 vertices and the following degrees: [latex]\text{deg}(A) = \text{deg}(C) = \text{deg}(D) = \text{deg}(F) = \text{deg}(G) = 2[/latex], [latex]\text{deg}(B) = \text{deg}(E) = 3[/latex]. Determine whether this graph contains an Euler cycle, an Euler path, or neither. Justify your answer using the necessary conditions for Euler cycles and paths. If an Euler cycle or path exists, explain how it could be constructed. If not, describe what changes would be needed to make one possible.
30. You are given a disconnected graph with 6 vertices and 2 components. Describe a strategy to add the minimum number of edges to make the graph connected. How many edges are needed, and why?

9.3 Directed Graphs

Basic Skills

31. What is a directed graph (digraph), and how does it differ from an undirected graph?
32. Given the edge [latex](A, B)[/latex], what does this tell you about the relationship between vertices [latex]A[/latex] and [latex]B[/latex] in a directed graph?
33. In a directed graph, vertex [latex]X[/latex] has incoming edges from vertices [latex]A[/latex], [latex]B[/latex], and [latex]C[/latex], and outgoing edges to vertices [latex]Y[/latex] and [latex]Z[/latex]. What are the indegree and outdegree of vertex [latex]X[/latex]?
34. Sketch a directed graph with 3 vertices [latex](A, B, C)[/latex] where [latex]A[/latex] points to [latex]B[/latex], [latex]B[/latex] points to [latex]C[/latex], and [latex]C[/latex] points to [latex]A[/latex]. Label all vertices and arrows.
35. In a directed graph, what does it mean if a vertex has an edge pointing to itself? What is this called?

Applications

36. A website is modelled as a directed graph where each page is a vertex, and each hyperlink is a directed edge. What does it mean if there is no path from the homepage to a certain page? How can this affect user experience?
37. In a project management system, tasks are represented as vertices and dependencies as directed edges. How does a directed graph help ensure tasks are completed in the correct order?
38. In an organization, each email sent is represented as a directed edge from sender to recipient. What does the indegree of a vertex represent in this context? What about the outdegree?
39. A program’s execution flow is modelled as a directed graph. Each function is a vertex, and each call from one function to another is a directed edge. How can this graph help identify unreachable code?
40. In a data processing pipeline, each module is a vertex and data transfer between modules is a directed edge. What does it mean if a module has an indegree of 0? What about an outdegree of 0?

Challenge Problems

41. A directed graph has vertices labelled [latex]A[/latex], [latex]B[/latex], [latex]C[/latex], [latex]D[/latex], [latex]E[/latex], and [latex]F[/latex]. The graph contains the following directed edges: [latex](A, B)[/latex], [latex](B, C)[/latex], [latex](C, D)[/latex], [latex](D, E)[/latex], [latex](E, F)[/latex], [latex](F, A)[/latex], [latex](A, C)[/latex], [latex](C, E)[/latex], [latex](E, A)[/latex]. Determine whether this directed graph contains a directed Euler cycle. Justify your answer by checking the necessary conditions for a directed Euler cycle. If one exists, describe a possible cycle. If not, explain what modifications would be needed to make one possible.
42. Given a directed graph with vertices [latex]A[/latex], [latex]B[/latex], [latex]C[/latex], [latex]D[/latex], and [latex](A, B)[/latex], [latex](B, C)[/latex], [latex](C, D)[/latex], [latex](D, B)[/latex] does the graph contain a cycle? Justify your answer and describe a method for detecting cycles in directed graphs.
43. A directed graph has 5 vertices. The sum of all incoming degrees is 12. What is the sum of all outgoing degrees? Explain why this must be true for any directed graph.
44. A directed graph represents task dependencies in a software build system. Tasks [latex]A[/latex], [latex]B[/latex], [latex]C[/latex], [latex]D[/latex], and [latex]E[/latex] have the following edges: [latex](A, B)[/latex], [latex](A, C)[/latex], [latex](B, D)[/latex], [latex](C, D)[/latex], [latex](D, E)[/latex]. Perform a topological sort of the tasks and explain why this ordering is valid.
45. A directed graph is used to model access control in a system. If vertex [latex]X[/latex] has no incoming edges and vertex [latex]Y[/latex] has no outgoing edges, what do these properties imply about [latex]X[/latex] and [latex]Y[/latex]? Propose a modification to the graph to ensure every vertex has at least one incoming and one outgoing edge.