Skip to content

4.30 Graph

  1. Let \(V = \{1, 2, ..., n\}\). How many different graphs on \(V\) are possible? How many graphs with exactly \(m\) edges are possible?

    In a complete graph \(K_n\) have \(\binom{n}{2}\) edges, every graph is specified by a function \(E:\{\binom{n}{2}\}\to\{0,1\}\)

    Then we have \(2^{\binom{n}{2}}\) such functions, there are \(\binom{\binom{n}{2}}{m}\) graph with exactly \(m\) edges

    Definition. Let \(G\) and \(H\) be two graphs. We say that \(G\) and \(H\) are isomorphic if there exists a bijection from the vertex set \(V(G)\) of \(G\) onto the vertex set \(V(H)\) of \(H\) so that the number of edges between \(a\) and \(b\) in \(G\) is equal to the number of edges between \(f(a)\) and \(f(b)\) in \(H\) for any \(a, b \in V(G)\).
    In that case, we call \(f\) an isomorphism from \(G\) into \(H\).

  2. Explain/prove the following.

    • Two isomorphic graphs have the same number of vertices and edges.

    Yes, bijection * Let \(G_1, G_2\) be two isomorphic graphs, and \(f : V_1 \to V_2\) the function that establishes the isomorphism. For any vertex \(v \in V_1\), the degree of \(v\) in \(G_1\) is equal to the degree of \(f(v)\) in \(G_2\).

    If \(v\in V\), then \(\deg(f(v))=\deg(v)\) then consider the definition of \(\deg\)​ * There exist four non-isomorphic graphs on 3 vertices.

    image​ * The following two graphs are isomorphic.

    image​

    image​

  3. There are seven houses in the village. Each house is connected to exactly three other houses by a path. Prove that this is not possible.

    We know the sum of degree is \(3\times 7=21\), then by handshaking lemma: \(\sum_{v\in V}\deg v=2\#E\)​

    Thus this is impossible

    By the way the same reason: Every graph should has even sum of vertices

  4. Suppose \(G\) is a connected graph. Show that \(|E| \ge |V| - 1\).

    If \(\Gamma\) is a connected graph with \(n\) vertices, then the number of its edges is \(\geq n-1\) by induction on vertices

    Or to prove it we can consider any connected graph has a spanning tree

    Every tree on \(n\) vertices has \(n-1\) edges, then every connected graph should contain a tree

  5. Some folklore character had 5 children. Among his descendants, 100 had exactly 3 children, all others left no children. How many descendants did this guy have?

    There will be not cycle since every cycle should have two distinct path, but it's clearly these two paths should go through Ivan

    image​

    The first equation is Sum of Total Degrees

    Sum of degrees = (Degree of IVAN) + (Sum of degrees of the 100) + (Sum of degrees of the 1)

    The second equation is Vertices and Edges in a Tree(\(\#E+1=\#V\))

    The number of vertices (#V) is the total number of people: IVAN (1 person) + the 100 descendants who had 3 children + the x descendants who had no children.

‍