Opening the book…
Use the figure to answer the following exercises.
List any graphs that are subgraphs of Graph U.
List any graphs that are subgraphs of Graph V.
Explain why Graph T is not a subgraph of Graph S.
List any graphs that have a quadrilateral cyclic subgraph and name the quadrilaterals.
Use the Sum of Degrees Theorem as needed to answer the following exercises.
How many edges are in a graph if the sum of the degrees of its vertices is 18.
Draw two possible graphs to demonstrate that the sum of the degrees of the vertices in a graph with 7 edges is 14. Label the degrees of the vertices.
What is the sum of the degrees of the vertices of a graph that has 122 edges?
A graph has 3 vertices of degree 2, 4 vertices of degree 1, and 2 vertices of degree 3. How many edges are in the graph?
There are 6 vertices and 11 edges in a graph, 2 of degree 5, 1 of degree 4, and 2 of degree 3. What is the degree of the remaining vertex?
A complete graph has 5 vertices. What is the sum of the degrees of the vertices?
A complete graph has 120 edges. How many vertices does it have?
Use the figure to answer the following exercises. Identify the graph or graphs with the given characteristic.
The sum of the degrees of the vertices is 16.
The graph is complete.
The graph has no cyclic subgraphs
The graph contains at least one octagon.
The graph contains exactly two 3-cycles.
Use the figure to answer the following exercises. Identify the graph or graphs with the given characteristic.
The graph is a subgraph of Graph 6.
The sum of the degrees of the vertices is 16.
The graph is complete.
The graph has no pentagons.
The graph contains at least one octagon.
The graph contains exactly two cyclic subgraphs.
Use Table 12.1 to name a heptagon in Graph 8.
Use the figure to answer the following exercises. Identify the graph or graphs with the given characteristic.
The sum of the degrees of the vertices is 16.
The graph is complete.
The graph contains exactly one quadrilateral.
The graph contains at least one octagon.
The graph contains exactly one cyclic subgraph.
Use Table 12.1 to answer the following exercises about the below figure.
List every quadrilateral in Graph 12.
List every quadrilateral in Graph 10.
Determine the number of quadrilaterals in Graph 9.
Use the figure to answer the following exercises.
Name five triangles in the graph.
Identify a clique with more than three vertices in the graph by listing its vertices.
For the following exercises, draw a graph with the given characteristics.
4 vertices, 6 edges, a subgraph that is a 4-cycle.
11 vertices, the only cyclic subgraphs are triangles.
Complete graph, no quadrilateral subgraph
4 vertices, 4 edges, no cyclic subgraphs
Complete graph, sum of the degrees of the vertices is 20.
7 vertices, largest clique has 5 vertices.
In chess, a knight can move in any direction, but it must move two spaces then turn and move one more space. The eight possible moves a knight can make from a space in the center of a five-by-five grid are shown in the first figure. Draw a graph that represents all the legal moves of a knight on a three-by-three grid starting from the lower left corner as shown in the second figure where the vertices will represent the spaces occupied by the knight and the edges will indicate a move from one space to the next.
What kind of cycle is the resulting graph you drew for Exercise 40?
Use Pascal’s triangle to find number of triangles in a complete graph with 14 vertices.
Do you think that a graph representing network of friends on Facebook is likely to be complete or not? Explain your reasoning.
Would the graph of a family tree, in which edges represent parent-child lineage, contain any cycles? Why or why not?
We have seen that the number of triangles in a complete graph with 7 vertices can be calculated using the pattern \((5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1=35\). This pattern gets very long for complete graphs with more vertices, but we have seen sums from 1 to a number before, and we had a shortcut! Recall from Example 12.8 that \(1+2+3+\cdots+(n-1)=\frac{n(n-1)}{2}\). This makes finding the sum from 1 up to \(n-1\) shorter. We can write each of the sums we need in the form \(\frac{n(n-1)}{2}\). To find the sum from 1 to 5 , since \(n-1=5\), use \(n=6: 1+2+3+4+5=\frac{6(5)}{2}\) To find the sum from 1 to 4 , since \(n-1=4\), use \(n=5: 1+2+3+4=\frac{5(4)}{2}\)
To find the sum from 1 to 3 , since \(n-1=3\), use \(n=4: 1+2+3=\frac{4(3)}{2}\)
To find the sum from 1 to 2 , since \(n-1=2\), use \(n=3: 1+2=\frac{3(2)}{2}\)
To find the sum from 1 to 1 , (Sounds silly, but it helps to see the pattern!) since \(n-1=1\), use \(n=2\) :
\[1=\frac{2(1)}{2} \nonumber \]
Use these to rewrite the calculation for the number of triangles in a graph with 7 vertices.
\[\begin{aligned}
& (5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1 \\
= & \underbrace{1}_{\frac{2(1)}{2}}+\underbrace{(1+2)}_{\frac{3(2)}{2}}+\underbrace{(1+2+3)}_{\frac{4(3)}{2}}+\underbrace{(1+2+3+4)}_{\frac{5(4)}{2}}+\underbrace{(1+2+3+4+5)}_{\frac{6(5)}{2}} \\
= & \frac{2(1)}{2}+\frac{3(2)}{2}+\frac{4(3)}{2}+\frac{5(4)}{2}+\frac{6(5)}{2} \\
= & \underbrace{\frac{1(2)+2(3)+3(4)+4(5)+5(6)}{2}}=35
\end{aligned} \nonumber \]
The number of triangles in complete graph with 7 vertices.
Similarly, for the number of triangles in a complete graph with 8 vertices, instead of
\[(6+5+4+3+2+1)+(5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1=56 \nonumber \]
use the shorter formula \(\frac{1(2)+2(3)+3(4)+4(5)+5(6)+6(7)}{2}=56\).
Use this pattern to find the number of triangles in a complete graph with 10 vertices. In which row and entry of Pascal's triangle can you also find this result?
Use the fact that the sum from 1 to \(n-1\) is \(\frac{n(n-1)}{2}\) to write a formula for the number of triangles in a complete graph with \(n\) vertices.
12.2.0: Exercises is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.
The book could not be loaded just now.