# Tagged Questions

42 views

### Face Boundary and bipartite question classification

Is this question wrong? Let G be a connected planar graph with a planar embedding where every face boundary is a cycle of even length. Prove that G is bipartite. Consider a graph of 2 squares ...
35 views

### Min. Spanning Tree - Same weight

Prove that every minimum spanning tree of a connected graph, $G$, has the same maximum edge. Intuitively, this makes sense to me. You need to have that heavy edge because that is the cheapest ...
33 views

### Stable Marriage - set of preferences such that every arrangement is stable?

This is a homework problem from the MIT OCW math for CS class, assignment 4, problem 5. Prove or disprove the following claim: for some n ≥ 3 (n boys and n girls, for a total of 2n people), there ...
34 views

58 views

### 3-pass counting triangles algorithm

Hei guys, I need some hints on Counting subgraphs in data streams. Consider this 3-pass counting triangles algorithm: 1st Pass: count the number of edges |E| in the stream 2nd Pass: sample ...
43 views

### Does the Cayley digraph $C$= [(12)(34),(123):$A_4$] have a Hamiltonian Circuit?

This is a problem I'm working on for a friend of mine. I haven't been able to solve it, or make much progress. I have drawn the digraph, and it consists of four directed cycles of three vertices all ...
35 views

### O(m) all-pairs shortest paths algorithm for directed acylical graph

An exercise I'm working on asks me to devise an $O(m)$ algorithm for the all-pairs shortest paths of the graph $G = (V, A)$, where $(v_i, v_j) \in A$ implies $i < j$. I'm wondering whether this is ...
70 views

### The chromatic number of a triangle-free graph.

Let $G$ be a triangle-free graph. Prove that $\chi(G)\leq3\lceil\dfrac{\Delta(G)+1}{4}\rceil.$ What's the relationship between the chromatic number and the maximum degree of a triangle-free graph ...
49 views

### Proving a triangle with different edge colors exists in a graph.

This is again some homework translated (hopefully not too badly) from my book The graph $K_{n}$ is colored using $n$ different colors, in a way that each color is used at least once. Prove that there ...
26 views

### Proof homomorphism between graphs

Given two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$, an homomorphism of $G_1$ to $G_2$ is a function $f:V_1 \rightarrow V_2$ such $(v,w) \in E_1 \rightarrow (f(v),f(w)) \in E_2$. We establish that ...
26 views

### Proof that a local minimum in a spanning tree is also a minimum spanning tree.

Be $G$ a connected graph with weights associated to its edges. Be $T(G)$ the graph that has the spanning trees of $G$ as vertex, and two spanning trees are adjacent to each other if and only if each ...
38 views

### 3-connected graph

Let $G$ be a 3-connected graph. Prove that for every three vertices $a, b, c$ of $G$ there exists a cycle in $G$ that contains $a,b$ but not $c$. Here is my work. Since $G$ is a 3-connected graph, ...
40 views

### Discrete Math True or False

1.$\mathcal P(A\setminus B) = \mathcal P(A) \setminus P(B)$ These are power sets. False. 2.If $G$ is bipartite, then the complement of $G$ is disconnected. False. 3.Suppose $\mathcal F$ and ...
81 views

### If a connected graph has a unique spanning tree, then it is a tree.

Prove if a connected graph has a unique spanning tree, then it is a tree. Edit: This can be shown with proof by contradiction.
29 views

### Let $G$ be a graph with radius $r$ and let $x$ be a vertex in the center of $G$. If $d$($x,y$)=$r$, then $y$ is in the periphery of $G$

Prove, disprove, or give a counterexample: Let $G$ be a graph with radius $r$ and let $x$ be a vertex in the center of $G$. If $d$($x,y$)=$r$, then $y$ is in the periphery of $G$. Eccentricity - the ...
63 views

### Maximal flow and minimal cut in complete graphs

The question is as follows: We define on the complete graph $K_n$ with the vertices {$v_1, v_2, ... , v_n$} the following directions: for every j>i, the edge $v_i v_j$ is directed from $v_i$ to ...
29 views

### Proof that any self-complementary graph has to have $4k$ or $4k+1$ vertex, for some $k \in \mathbb N$

I've seen looking on previous questions that using this algorithm, I can construct self-complementary graphs. I got confused at this point, because I'm not sure if I should proof that there are no ...
38 views

### Finding quantity of vertex of odd degree in a graph

Let $G=(V,X)$. If $G$ has n vertex, such exactly $n-1$ have odd degree, how many vertex of odd degree have $\overline {G}$. ($\overline {G}$ the complement of $G$.) So the first thing I notice is ...
61 views

### 2-Connected Graph

I am asked to prove that every connected, bipartite, k-regular ($k \ge2$) graph is 2-connected. Now for $n \ge 3$ I can use few of the theorems included and show that it is so indeed (focusing on the ...
16 views

### Proof that in a graph of $2$ or more vertrex, there's at least $2$ of them that have the same degree

That's what I what to prove let $G$ be an undirected graph such it has $2$ or more vertex, there's at least $2$ vertex that have the same degree. I'm almost certain that, supposing that it's possible ...
52 views

### Prove a 4-cycle exists in a graph with 100 vertices, each with degree of atleast 50

I hope I wrote the question well since it is my attempt at translating from the book. If it isnt clear enough, The question states that in every graph as described in the title a simple cycle of ...
23 views

### Expected number of connections for a graph

If I have a graph with 10 nodes and probability of an edge being 0.6, what is the expected number of 'common friends' of two nodes A and B? e.g. by 1 common friend I mean that for Node A and B (just ...
76 views

### Number of connections for a graph

Suppose we have a graph $G(12,0.7)$ where 12 is the number of nodes and 0.7 is the probability of an edge being present. So total number of edges = $\binom{12}{2} = 66$ Q1 (SOLVED): What is the ...
101 views

### Finding minimum graph of $k$ disjoints component

Sorry for the english, I tried to make it the most clear possible. Be $G$ a connected graph not directed, I have to find an algorithm that given $n$ the quantity of vertex and $0<k<n$ disjoint ...
66 views

### Thickness of G when G is a simple connected graph

The thickness of a simple graph G is the smallest number of planar subgraphs of G that have G as their union. Show that if G is a connected simple graph with v vertices and e edges, where v ≥ 3, then ...
Given a finite graph $G$ which is bipartite with partitions $A$ and $B$ and has no vertices without edges. For any neighbouring $x \in X$ and $y\in Y$ it holds that $\operatorname{deg} x \geq ... 0answers 26 views ### prove splits compatible if and only if edge-split "Prove that if$e_A$and$e_B$are distinct edges of a binary$X$-tree$T$and$C=A\Delta B$(symmetric difference), then the splits$\sigma(A), \sigma(B)$and$\sigma(C)$are compatible if and only if ... 1answer 14 views ### Mean number of FFL subgraphs with one output node So, this is a Feed Forward Loop. It is a regularly occurring subgraph of a huge random graph. In the case of X,Y,Z being any nodes, we have that the mean number of times that a subgraph G appears is ... 2answers 136 views ### Every planar graph has a vertex of degree at most 5. I am trying to prove the following statement, any help!? Prove that every planar graph has a vertex of degree at most 5. 3answers 73 views ### Graph Theory - Proof - Isomorphism [closed] If anyone can help me prove the following: Suppose that$G$is a plane graph which is isomorphic to its dual. Prove that$G$has$2n-2$edges. I thank you for your time! 1answer 35 views ### Graph Theory Question Related to Domination number. Let G be a graph whose diameter is at least 3. Prove that the domination number of the complement of G is at most 2. I know that since the diameter of G is at least 3, the diameter of the complement ... 1answer 31 views ### Expected number of feed-forward/backward triangles in a random graph with internal nodes. Suppose we have a graph with N* nodes (these are internal nodes. they all have at least one child). Every directed link in the network exists with probability p. What would be the expected number of: ... 0answers 57 views ### Maximum number of edges in a (n,n) bipartite graph, that doens't have a complete bipartite subgraph$K_{r,r}$I need to prove that the maximum number of edges in a$n \times n$bipartite graph, that doens't have a complete bipartite subgraph$K_{r,r}$is lower bounded by$cn^{2-2/(r+1)}$where c is a constant ... 0answers 74 views ### Prove that a certain graph and its dual are 4-colorable Let$G$be a simple planar graph with fewer than 12 faces. Suppose that each vertex of$G$has degree at least$3$. prove that$G$and its dual are 4-colorable. I'm not too sure how to approach ... 2answers 268 views ### what is the maximum number of non loop edges that can exist in an undirected graph please tell me a equation to find maximum number of non loop edges that can exist in an undirected graph. for example if vertices are 10 then how many non loop edges can exist? 2answers 84 views ### Given a directed graph, count the total number of paths of ANY length Given a directed graph, how to count the total number of paths of ANY possible length in it? I was able to compute the answer using the adjacency matrix$A$, in which the number of paths of the ... 1answer 65 views ### Algebraic Combinatorics Let$K_{r,s}$denote the complete bipartite graph, deﬁned on$r + s$vertices$\{v_1,v_2,...,v_r,w_1,...,w_s\}$, with an edge between$v_i$and$w_j$for$1 ≤ i ≤ r$and$1 ≤ j ≤ s$. By ... 1answer 45 views ### Colouring bipartite graph with sets of possible colors to each vertex I'm having some trouble with proving the following: Let$|S(v)|$be the set of colours available to colour vertex v. The claim is that for every bipartite graph$G=(V,E)$, if$|S(v)| > log_2n$for ... 2answers 37 views ### I'm not quite sure I understand my book's reasoning for the answer I have the following homework problem: Does there exist a graph,$G$, with 28 edges and 12 vertices, each of degree 3 or 4? First, my solution.$$\sum deg(v_i) = 2 \cdot |E| \\ |E| = 28 ... 1answer 71 views ### The number of edges this graph Let$G$be a graph with$V(G)=\{d_i;d_i|n,d_i\not=1,n\}$and$E(G)=\{d_id_j;d_i|d_j ~or~d_j|d_i\}.$Here$n$is the natural number.I know that if$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots ...
Prove if $G=(E,V)$ is a 4-regular connected graph then $G$ has two spanning graph $G_1(E_1,V)$ and $G_2(E_2,V)$ such as: $\mathbf 1.$ $\forall$ $v$ $\in$ $V$ in $G_1$ and $G_2$ $deg(v) = 2$ . ...