StudyFox
कीमतेंब्लॉगएक्सटेंशनमुफ़्त टूल
  • कीमतें
  • ब्लॉग
  • एक्सटेंशन
  • मुफ़्त टूल
  • शुरू करेंसाइन इन
StudyFox

अपने नोट्स, PDF और स्लाइड्स को फ़्लैशकार्ड, क्विज़, नोट्स और माइंड मैप में बदलें।

StudyFox खोलें

स्टडी टूल्स

  • होमवर्क हेल्पर
  • नोट मेकर
  • फ़्लैशकार्ड मेकर
  • क्विज़ मेकर
  • माइंड मैप मेकर

प्रोडक्ट

  • कीमतें
  • Chrome एक्सटेंशन
  • मुफ़्त एक्सटेंशन
  • स्टडी सेट देखें
  • ब्लॉग

सहायता

  • सहायता केंद्र
  • संपर्क करें
  • गोपनीयता नीति
  • सेवा की शर्तें

तुलना करें

  • Chegg का विकल्प
  • Course Hero का विकल्प
  • Coursology का विकल्प
  • Photomath का विकल्प
  • Gauthmath का विकल्प
  • PhotoSolve का विकल्प
  • CollegeTools का विकल्प
  • Transcript का विकल्प
  • SmartSolve का विकल्प
  • Homeworkify का विकल्प
  • AnswersAi का विकल्प
  • StudyX का विकल्प
  • Quizlet का विकल्प
  • Anki का विकल्प
  • Knowt का विकल्प
  • Brainscape का विकल्प
  • सभी तुलनाएँ

© 2026 StudyFox AI. सर्वाधिकार सुरक्षित।

  • X
  • Discord
  • Instagram
ExploreMathDiscrete MathDiscrete Math Quiz: Graph Theory Fundamentals

Quiz · Medium

Discrete Math Quiz: Graph Theory Fundamentals

Twenty questions on degrees, Euler and Hamilton circuits, trees, spanning trees, planarity, coloring and traversal.

by Kill h.20 questionsCreated Nov 20, 2026, 08:27 PM
Discrete Math· Graph TheoryTags#graph-theory#trees#euler#coloring

20 questions

  1. 1

    A tree has 20 vertices. How many edges does it have?

    • A

      18

    • 19

    • C

      20

    • D

      21

    A tree on n vertices always has n - 1 edges: 19.

  2. 2

    A simple graph has 8 edges. What is the sum of its vertex degrees?

    • A

      8

    • B

      12

    • C

      64

    • 16

    Each edge contributes 1 to the degree of each endpoint, so the degree sum is 2 * 8 = 16 (handshake lemma).

  3. 3

    How many edges does have?

    • 21

    • B

      14

    • C

      42

    • D

      49

    C(7, 2) = 7 * 6 / 2 = 21. 42 counts ordered pairs, which double counts each edge.

  4. 4

    Which graph has an Euler circuit?

    • A

    • B

    • D

      a path on 5 vertices

    A connected graph has an Euler circuit iff all degrees are even. K5 is 4-regular. K4 and K3,3 are 3-regular (odd); a path has two vertices of degree 1.

  5. 5

    The Konigsberg bridge graph has vertex degrees 5, 3, 3, 3. Why is there no Euler path?

    • A

      The graph is disconnected

    • It has 4 odd-degree vertices, but an Euler path allows at most 2

    • C

      It contains a vertex of degree 5

    • D

      It has fewer than 8 edges

    An Euler path needs 0 or 2 odd-degree vertices; here all four are odd. The graph is connected, and a degree-5 vertex is fine by itself.

  6. 6

    The graph in the picture is

    • B

    • C

    • D

      the 6-cycle

    Two rows of 3 vertices with every top vertex joined to every bottom vertex: K3,3, with 9 edges. It is bipartite and non-planar. Image: public domain, via Wikimedia Commons.

  7. 7

    What is the chromatic number of an odd cycle ?

    • A

      2

    • B

      4

    • C

      7

    • 3

    Even cycles are 2-colorable, but with an odd cycle the colors alternate around and clash at the end, so 3 are needed (and enough).

  8. 8

    Which statement about bipartite graphs is true?

    • A

      They contain at least one triangle

    • B

      They are always trees

    • They contain no odd cycle

    • D

      They have an Euler circuit

    A graph is bipartite exactly when it has no odd-length cycle. Trees are bipartite but not all bipartite graphs are trees (K3,3 is not).

  9. 9

    A connected planar simple graph has V = 6 and E = 9. How many faces does it have?

    • A

      3

    • 5

    • C

      4

    • D

      6

    Euler's formula V - E + F = 2 gives F = 2 - 6 + 9 = 5.

  10. 10

    Why is not planar?

    • It has 10 edges, more than 3V - 6 = 9

    • B

      It has an odd number of vertices

    • C

      It has no triangles

    • D

      It is not connected

    A simple planar graph on V >= 3 vertices has at most 3V - 6 edges. K5 has 10 > 9.

  11. 11

    Prim's and Kruskal's algorithms both produce

    • A

      a shortest path tree from a source

    • B

      a maximum matching

    • C

      an Euler circuit

    • a minimum spanning tree

    Both are greedy algorithms that build a minimum-weight spanning tree. Shortest-path trees come from Dijkstra (they can differ from MSTs).

  12. 12

    This weighted graph has its minimum spanning tree in red. What is the weight of the MST?

    • A

      18

    • B

      22

    • 20

    • D

      25

    The red edges weigh 1 + 2 + 3 + 3 + 5 + 6 = 20. Image: Illes, public domain, via Wikimedia Commons.

  13. 13

    A full binary tree has 15 leaves. How many internal vertices does it have?

    • A

      7

    • 14

    • C

      15

    • D

      16

    Leaves = internal + 1 for a full binary tree, so internal = 14 (and 29 vertices in total).

  14. 14

    The inorder traversal of the binary tree is

    • A

      F B A D C E G I H

    • B

      A C E D B H I G F

    • C

      F B G A D I C E H

    • A B C D E F G H I

    Inorder visits left subtree, node, right subtree, which gives A B C D E F G H I here. The second option is preorder, the third postorder and the fourth level-order. Image: Moberg, public domain.

  15. 15

    Which algorithm finds shortest paths in a graph with non-negative weights?

    • Dijkstra

    • B

      Kruskal

    • C

      Hall's algorithm

    • D

      Topological sort

    Dijkstra's greedy algorithm repeatedly finalizes the nearest unfinished vertex. Kruskal builds an MST.

  16. 16

    True or false: every connected graph has a spanning tree.

    • True

    • B

      False

    Repeatedly delete an edge from any cycle; the graph stays connected and eventually becomes a tree on the same vertices.

  17. 17

    Using BFS from vertex 1 (smaller neighbors first) on the graph with edges 1-2, 1-3, 2-4, 2-5, 3-6, 3-7, 5-6, which vertex is visited last?

    • A

      4

    • B

      5

    • 7

    • D

      6

    BFS visits level by level: 1; then 2, 3; then 4, 5 (from 2) and 6, 7 (from 3). The order is 1, 2, 3, 4, 5, 6, 7 so 7 is last. The edge 5-6 does not change the levels. (Drawn graph.)

  18. 18

    The number of labeled trees on 5 vertices is

    • 125

    • B

      25

    • C

      60

    • D

      3125

    Cayley's formula: n^(n-2) = 5^3 = 125.

  19. 19

    The graph with two odd-degree vertices (the bottom corners) in the picture has

    • A

      an Euler circuit

    • an Euler path but no Euler circuit

    • C

      neither an Euler path nor an Euler circuit

    • D

      an Euler circuit but no Euler path

    Exactly two vertices have odd degree, so an Euler path exists (from one odd vertex to the other), but no Euler circuit. Image: Fschwarzentruber, CC BY-SA 4.0, via Wikimedia Commons.

  20. 20

    A graph has a Hamilton cycle if every vertex has degree at least n/2 (n >= 3). This is

    • A

      Euler's theorem

    • B

      Hall's theorem

    • Dirac's theorem

    • D

      Kuratowski's theorem

    Dirac's theorem gives a sufficient (not necessary) condition for a Hamilton cycle.