Unit 4: Graphs Theory I - Practice Quiz

1 What is the degree of a vertex in an undirected graph?

2 What are two vertices called if an edge connects them?

3 A vertex with degree is called what?

4 How many edges does the complete graph have?

5 Which statement describes a cycle graph?

6 What is a regular graph?

7 How is a wheel graph formed from a cycle graph?

8 How many vertices does the three-dimensional cube graph have?

9 What property defines a bipartite graph?

10 How many edges are in the complete bipartite graph ?

11 Which representation lists the neighbors of each vertex?

12 For a simple undirected graph, what does an entry in an adjacency matrix indicate?

13 What is always true about the adjacency matrix of a simple undirected graph?

14 In the incidence matrix of a simple undirected graph, what do the columns usually represent?

15 When are two graphs isomorphic?

16 Which property must be the same for two isomorphic graphs?

17 What is a path in a graph?

18 When is an undirected graph connected?

19 When is a directed graph strongly connected?

20 Which condition is required for Dijkstra's shortest path algorithm to work correctly?

21 A simple undirected graph has 12 vertices, each of degree 5. How many edges does the graph contain?

22 A simple graph has 8 vertices and 13 edges. What is the number of edges in its complement?

23 A complete graph has 45 edges. How many vertices does it have?

24 A wheel graph is formed by adding one hub vertex adjacent to every vertex of . Which statement describes the resulting graph?

25 Which pair gives the degree of each vertex and the total number of edges in the 3-dimensional cube graph ?

26 In the complete bipartite graph , which statement is correct?

27 A connected graph contains exactly one cycle, and that cycle has length 7. Which conclusion is necessarily true?

28 An undirected graph has adjacency list , , , and . Which edge set represents the graph?

29 The adjacency matrix of a simple undirected graph is What are the degrees of vertices 1 through 4?

30 The incidence matrix of a simple undirected graph has 7 rows and 10 columns. What do these dimensions indicate?

31 For a loop-free directed graph, the adjacency matrix uses when there is an arc from vertex to vertex . What does the sum of column represent?

32 Graph has edges , and graph has edges . Which mapping is an isomorphism from to ?

33 Two simple graphs have the same degree sequence . One graph is , while the other consists of two disjoint triangles. Why are they not isomorphic?

34 In a graph with edges , consider the sequence . How should this sequence be classified?

35 A connected graph has 9 vertices and 9 edges, with exactly one cycle. An edge on that cycle is removed. What is true of the resulting graph?

36 A digraph has arcs , , , and . Which statement is correct?

37 An undirected connected graph has a bridge . What happens when is removed?

38 A weighted undirected graph has edges , , , , , , and . What is the shortest distance from to ?

39 During Dijkstra's algorithm, vertex has finalized distance 6. An edge from to an unvisited vertex has weight 4, while the current tentative distance of is 13. What is the updated distance of ?

40 Why can the standard Dijkstra's algorithm fail when a graph contains a negative-weight edge?

41 Which of the following nonincreasing sequences is graphical for a simple graph on six vertices?

42 A simple graph has ten vertices: six vertices have degree , and four vertices have degree . How many edges does the line graph have?

43 Let be formed by adjoining one hub vertex to every vertex of the cycle , where . For which value of is regular?

44 In the -dimensional cube graph , what are, respectively, the number of shortest paths and the maximum number of internally vertex-disjoint paths between two antipodal vertices?

45 How many distinct spanning trees does the complete bipartite graph have?

46 A simple graph on nine vertices is regular and isomorphic to its complement. Which pair gives the degree of each vertex and the number of edges of ?

47 Let be the adjacency matrix of a graph under its original labeling. A new labeling is specified by a permutation matrix whose th column is the standard basis vector corresponding to the old label of new vertex . What is the adjacency matrix under the new labeling?

48 Let be the adjacency matrix of the cycle . What is the value of the entry ?

49 An undirected graph has vertices, edges, and connected components. After assigning an arbitrary orientation to every edge, let be its oriented incidence matrix over . What are and ?

50 A simple graph has edges, degree sequence , and adjacency matrix satisfying . How many distinct -cycles does the graph contain?

51 Graph is obtained from by adding chords and . Graph is obtained from by adding chords and . Both graphs use the cyclic order . Which invariant proves that and are not isomorphic?

52 Let have edge set and let have edge set . Which tuple defines an isomorphism ?

53 In , let belong to the part of size and belong to the part of size . What is the maximum number of pairwise internally vertex-disjoint - paths?

54 The condensation of a digraph has vertices and arcs , , , , , and . What is the minimum number of arcs that must be added to make the original digraph strongly connected?

55 A finite digraph has a condensation DAG containing exactly one source strongly connected component . Which conclusion is necessarily true?

56 Consider the directed weighted graph with arcs , , , , , , , and . What are the shortest distance from to and the number of distinct shortest - paths?

57 A directed graph has arcs , , , , and . If standard Dijkstra's algorithm finalizes vertices and stops when is extracted, what distance does it report for , and what is the true shortest distance?

58 Dijkstra's algorithm is run on a graph with nonnegative edge weights, including zero-weight edges, and equal tentative distances are broken arbitrarily. Which property is guaranteed?

59 Which transformation of all edge weights is guaranteed to preserve the complete set of shortest paths between every ordered pair of vertices in a nonnegatively weighted graph?

60 In an undirected graph, two nonadjacent vertices and are connected by at most four pairwise internally vertex-disjoint - paths, and a family of four such paths exists. What is the minimum size of a vertex set, excluding and , whose removal separates from ?