0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
34 views

Homomorphism from a commutative group?

I came across this question in a practice exercise and can't quite understand it. If f is a homomorphism from a commutative group $(S,*)$ to another group $(T,*')$, then prove that $(T,*') is also ...
1
vote
2answers
36 views

graph theory: show that for k=4 hesse diagram is not a planar graph

In this picture you can see the hesse diagrem of $\subseteq$ over $P(\{x,y,z\})$ For the set $A$ with $k$ elements, $k>0$ look at the diagram as a graph, it's vertices are the members of $P(A)$ ...
0
votes
1answer
18 views

graph theory: the degree of vertices in an hesse diagrem graph

In this picture you can see the hesse diagrem of $\subseteq$ over $P(\{x,y,z\})$ For the set $A$ with $k$ elements, $k>0$ look at the diagram as a graph, it's vertices are the members of $P(A)$ ...
1
vote
0answers
33 views

Strongly regular tournament

A digraph on $n$ vertices is called a tournament if there is a exactly one directed edge between any two distinct vertices. A vertex $v$ dominates a vertex $w$ if there is an edge from $v$ to $w$. ...
3
votes
0answers
34 views

An undirected graph $G$ can be decomposed into simple edge-disjoint cycles if and only if all of its vertices have even degree.

Research effort: $\rightarrow)$ I think this is relatively easy. $\leftarrow)$ Let $G = (V,E)$, let $w$ be any vertex of $G$, given that all the vertex have even degree, I'm assured that I can ...
2
votes
1answer
47 views

Graphs without nontrivial automorphism

I'm trying to solve two problems about graph automorphisms. I want to construct a bipartite graph without a nontrivial automorphism. I want to find the smallest possible number of nodes for a graph ...
3
votes
1answer
60 views

Error in my reasoning on $\dim_{VC}(H)=1\Rightarrow|H|\leq 1$?

Let $S$ be a set with $n$ elements. Let $P(S)=\{X\mid X\subseteq S\}$ Let $H\subseteq\mathcal{P}(S)$ (hypergraph with edge set $S$). Let $H_{|U}=\{U\cap A\mid A\in H\}$ Let ...
0
votes
1answer
40 views

Graphs Theory Hint about k-connected

Show That G is a k-edge-connected graph if and only if there is no non-empty proper subset W to V (G), such that the number of edges joining W to V (G) - W is less k. Can anyone help me or give me a ...
0
votes
1answer
25 views

Prove that if graph G is connectivity so for any 3 vertices $v,u,w$ :$ d(v,w)+d(w,u) \geq d(v,u)$

d(v,u) denotes the shortest distance between 2 vertices: v,u. Prove that if graph G is connected, so for any 3 vertices v,u,w : $d(v,w)+d(w,u) \geq d(v,u)$. Any help will be much appreciated.
0
votes
1answer
39 views

A proof regarding connected components of a graph

Been struggling with this home-work question for some days now. Will appreciate an explanation. Let $c(G)$ denote the amount of connected components in a graph $G$. a. prove that $\forall e\in E: ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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, ...
0
votes
1answer
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 ...
3
votes
3answers
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.
0
votes
1answer
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 ...
4
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
73 views

bipartite graph and size of partitions

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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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.
-4
votes
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!
0
votes
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 ...
0
votes
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: ...
2
votes
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 ...
0
votes
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 ...
0
votes
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?
0
votes
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 ...
2
votes
1answer
65 views

Algebraic Combinatorics

Let $K_{r,s}$ denote the complete bipartite graph, defined 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 ...
3
votes
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 ...
0
votes
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 ...
2
votes
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 ...
0
votes
1answer
28 views

Finding two spanning graphs in a 4-regular connected graph

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$ . ...