Scribd Logo
Upload

Welcome to Scribd!

  • 16 views

    Cycles in Graphs

    Uploaded by

    poghosyan.milanna
    This document discusses cycles in graphs and presents 15 problems related to proving properties about cycles. It begins with 4 lemmas about cycles in graphs and their relationship to properties like degree and bipartiteness. The remainder of the document outlines 15 problems, the goal of the last 5 being to prove the Erdös–Gallai theorem about the minimum number of edges needed to guarantee a cycle of a given length.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Cycles in Graphs

    Uploaded by

    poghosyan.milanna
    16 views2 pages
    This document discusses cycles in graphs and presents 15 problems related to proving properties about cycles. It begins with 4 lemmas about cycles in graphs and their relationship to properties like degree and bipartiteness. The remainder of the document outlines 15 problems, the goal of the last 5 being to prove the Erdös–Gallai theorem about the minimum number of edges needed to guarantee a cycle of a given length.

    Original Title

    Cycles_in_graphs

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses cycles in graphs and presents 15 problems related to proving properties about cycles. It begins with 4 lemmas about cycles in graphs and their relationship to properties like degree and bipartiteness. The remainder of the document outlines 15 problems, the goal of the last 5 being to prove the Erdös–Gallai theorem about the minimum number of edges needed to guarantee a cycle of a given length.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    16 views2 pages

    Cycles in Graphs

    Uploaded by

    poghosyan.milanna
    This document discusses cycles in graphs and presents 15 problems related to proving properties about cycles. It begins with 4 lemmas about cycles in graphs and their relationship to properties like degree and bipartiteness. The remainder of the document outlines 15 problems, the goal of the last 5 being to prove the Erdös–Gallai theorem about the minimum number of edges needed to guarantee a cycle of a given length.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Cycles in graphs

    Radoslaw Żak
    17th June 2021

    1 Introduction
    Lemma 1. All vertices in a graph have degree 2 ⇒ graph is a disjoint union of
    cycles.
    Lemma 2. Graph with n vertices and n edges has a cycle.

    Lemma 3. Directed graph in which degout v > 1 for any vertex v, has a cycle.
    Lemma 4. G is bipartite ⇐⇒ G has no odd cycles.

    2 Problems
    1. On a m × n grid m + n cells are marked. Prove that we can choose some
    subset A of marked cells, such that any row and any column has even
    number of elements of A.
    2. A graph G has no cycle of length 3, and none of its induced subgraphs is a
    path with four vertices. Prove that if G is connected, then it’s a complete
    bipartite graph.
    3. On an infinite grid 111 L-triominos were placed, in such a way that for
    any triomino the square 2 × 2 containing it is fully covered. Prove that we
    can delete one triomino, so that this property will still hold.

    4. Prove that in a graph with 2n + 1 vertices and 3n + 1 edges there is an


    even cycle.
    5. In a tournament G = (V, E) for any partition V = A ∪ B we can find
    a ∈ A, b ∈ B with an edge a → b. Prove that G has a Hamiltonian cycle.

    6. Cells of a n × n grid was filled with real numbers so that rows are pairwise
    distinct. Prove that we can erase some column, so that rows will stay
    pairwise distinct.

    1
    7. A tournament G has n > 2022 vertices. Prove that there is a sequence
    of vertices of G, not necessarily distinct (!), A1 , A2 , . . . , An , such that for
    any i we have edges Ai → Ai+1 and Ai → Ai+2021 (of course for such i
    that these indices are well-defined) (in particular Ai+1 6= Ai 6= Ai+2021 ).

    8. Prove that in a graph G = (V, E), which is not bipartite and has no cycles
    of length 3, there is a vertex of degree 6 2n
    5 , where n = |V |.

    9. Graph G is 3-regular and connected. Prove that we can erase edges of


    some cycle, so that G will stay connected.

    10. Edges of a tournament were colored with two colors. Prove that there is a
    vertex, such that starting there we can reach any other vertex using path
    of one color.

    The goal of the next five problems is to prove Erdös–Gallai theo-


    rem (problem 15). You are welcome to use statement of the problem
    n in solving the problem n + 1.

    11. Graph G has a Hamiltionian cycle A1 A2 . . . An A1 . We know that there


    is no Hamiltonian path starting in Ai and ending in Aj (for some i 6= j,
    i, j ∈ {1, 2, . . . , n}). Prove that deg Ai+1 + deg Aj+1 6 n.
    12. Graph G has a Hamiltonian cycle P A1 A2 . . . An−1 P . Let us call a vertex
    Ai a Hamiltionian vertex, if there is a Hamiltonian path starting in P and
    ending in Ai . Prove that if Ai > k for every i, and n 6 2k − 1, then every
    vertex Ai is Hamiltonian.1
    13. In graph G let us choose a vertex P . A loop would be a way of a form
    P A1 A2 . . . Am Am+1 . . . An Am . A cycle of a loop is C = Am Am+1 . . . An Am .
    Take a longest loop starting at P (if some loops have the same length,
    take the one with the largest cycle). Prove that if the cycle of this
    loop has length 6 2k − 1, and every vertex of G has degree > k, then
    Am+1 Am+2 . . . An is a connected component of graph G \ {Am }.
    14. Every vertex of a 2-connected graph G has a degree > k, and |G| > 2k.
    Prove that G has a cycle of length > 2k.
    15. Graph G has n vertices. Choose integer k > 2. Prove that if G has more
    than (n−1)k
    2 edges, then it has a cycle of length greater than k.

    1 Note that we have no assumption about degree of P .

    You might also like