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 Problems (Hard)

Quiz · Hard

Discrete Math Quiz: Graph Theory Problems (Hard)

Fifteen harder graph theory questions: degree sequences, Dirac's theorem, planar edge bounds, tree counting, Hall's theorem, shortest paths and traversals.

by Kill h.15 questionsCreated Nov 20, 2026, 08:28 PM
Discrete Math· Graph TheoryTags#graph-theory#planar#hall#dijkstra

15 questions

  1. 1

    A full 3-ary tree has 10 internal vertices. How many leaves?

    • A

      20

    • B

      29

    • 21

    • D

      31

    For a full m-ary tree l = (m - 1)i + 1 = 2 * 10 + 1 = 21 (total vertices 31).

  2. 2

    A simple graph has degree sequence (4, 4, 3, 3, 2, 2, 2). How many edges does it have, and is the sequence possible?

    • A

      10 edges; impossible

    • B

      20 edges; possible

    • C

      9 edges; possible

    • 10 edges; possible

    Sum = 20, so E = 10 (even sum is necessary). Havel-Hakimi: remove 4 -> (3,2,2,1,2,2) -> sorted (3,2,2,2,2,1); remove 3 -> (1,1,1,2,1) -> sorted (2,1,1,1,1); remove 2 -> (0,0,1,1) -> fine. So it is graphical.

  3. 3

    A connected simple graph has 12 vertices and every vertex has degree 6. Which theorem guarantees a Hamilton cycle?

    • A

      Euler's theorem

    • B

      Cayley's formula

    • Dirac's theorem

    • D

      Euler's formula

    Each degree 6 = n/2 meets Dirac's condition (degree >= n/2 for n >= 3). Euler's theorem is about edges, not vertices.

  4. 4

    A planar graph with 10 vertices has no triangles. The maximum possible number of edges is

    • 16

    • B

      18

    • C

      24

    • D

      27

    With no triangles every face has at least 4 edge-sides, so E <= 2V - 4 = 16. The general bound 3V - 6 = 24 applies only if triangles are allowed.

  5. 5

    A connected planar graph has all faces bounded by exactly 4 edges (including the outer face). If V = 8, what are E and F?

    • A

      E = 14, F = 8

    • E = 12, F = 6

    • C

      E = 16, F = 10

    • D

      E = 10, F = 4

    4F = 2E gives E = 2F. Euler: 8 - 2F + F = 2 so F = 6, E = 12. This is the cube.

  6. 6

    How many distinct Hamilton cycles (undirected, no fixed start) does have?

    • A

      24

    • B

      120

    • 60

    • D

      720

    (n - 1)!/2 = 5!/2 = 60.

  7. 7

    The chromatic number of the wheel (a 5-cycle plus a hub joined to all rim vertices) is

    • 4

    • B

      2

    • C

      3

    • D

      5

    The rim is an odd cycle needing 3 colors, and the hub is adjacent to every rim vertex so needs a 4th.

  8. 8

    The Petersen graph (10 vertices, 3-regular) has how many edges and what is its chromatic number?

    • A

      15 edges; chi = 4

    • 15 edges; chi = 3

    • C

      30 edges; chi = 3

    • D

      10 edges; chi = 2

    E = 10 * 3 / 2 = 15. It contains 5-cycles so chi >= 3, and the picture shows a 3-coloring. Image: public domain, via Wikimedia Commons.

  9. 9

    How many spanning trees does the 4-cycle have?

    • A

      3

    • B

      6

    • C

      16

    • 4

    Remove any one of the 4 edges: each gives a distinct spanning path. (By contrast K4 has 4^2 = 16.)

  10. 10

    In the weighted graph (edges AB 4, AC 2, BC 1, BD 5, CE 8, DE 2, DF 3, EF 3), the shortest path from A to F has length

    • A

      9

    • B

      12

    • C

      13

    • 11

    A-C-B-D-F = 2 + 1 + 5 + 3 = 11. The route via E costs at least 13 (A-C-B-D-E-F = 13 or A-C-E-F = 13).

  11. 11

    A tree has exactly 4 vertices of degree 3 and no vertices of degree 2 or more than 3. How many leaves does it have?

    • 6

    • B

      4

    • C

      8

    • D

      10

    Let L leaves (degree 1). Degree sum = 12 + L = 2(n - 1) with n = 4 + L, so 12 + L = 2(3 + L) = 6 + 2L, giving L = 6.

  12. 12

    Which condition guarantees a bipartite graph with sides X and Y has a matching covering all of X?

    • A

      every vertex has even degree

    • for every subset S of X, |N(S)| >= |S|

    • C

      the graph is a tree

    • D

      |X| = |Y|

    That is Hall's condition, and it is necessary and sufficient. Equal side sizes alone do not help: two vertices may share a single neighbor.

  13. 13

    The preorder traversal of the binary tree is

    • A

      A B C D E F G H I

    • F B A D C E G I H

    • C

      A C E D B H I G F

    • D

      F G B I D A H E C

    Preorder visits the root first, then the left subtree, then the right: F, B, A, D, C, E, G, I, H. Image: Moberg, public domain.

  14. 14

    The red edges in the picture form a

    • A

      Hamilton cycle

    • B

      spanning tree

    • matching that is maximum

    • D

      perfect matching

    The three red edges share no endpoints, so they form a matching. It is maximum because the upper side has only 3 vertices. It is not perfect since the lower side has 4 vertices, one uncovered. Image: Illes, public domain.

  15. 15

    For which n does the complete graph (n >= 3) have an Euler circuit?

    • only odd n

    • B

      all n

    • C

      only even n

    • D

      only n = 3

    Each vertex has degree n - 1, which is even exactly when n is odd.