Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

0
votes
0answers
9 views

Let $d_1,d_2,…,d_n$be positive integers, with $n\geq 2$. Prove that there exists a tree with vertex [duplicate]

Let $d_1,d_2,...,d_n$ be positive integers, with $n\geq 2$. Prove that there exists a tree with vertex degrees $d_1,d_2,...,d_n$ if and only if $\sum d_i= 2n-2$. I have no idea how to prove this ...
2
votes
2answers
31 views

Deriving the number of edges in a Turán graph

When stating Turán's theorem, the Turán graphs are often used to give an upper bound on the possible number of edges in a graph without a clique of a certain size. This bound can also be proven ...
1
vote
0answers
26 views

(Proof Verification) Prove There Is A Hamiltonian Cycle for Every $n$ dimensional hypercube where $n\geq2$

Prove There Is A Hamiltonian Cycle for Every $n$ dimensional hypercube where $n\geq2$ My book gave a very fancy proof by induction, but to me it seems obvious that if we simply follow the standard ...
0
votes
1answer
1k views

Proving that a Euler Circuit has a even degree for every vertex

Theorem: Given a graph G has a Euler Circuit, then every vertex of G has a even degree Proof: We must show that for an arbitrary vertex v of G, v has a positive even degree. What does it ...
1
vote
0answers
7 views

Approximation for the minimal test cover / minimal group test problem

There are multiple approximation methods I find for the minimal test cover, where approximation is with respect to the size of the test set. However I am looking for approximation which starts with a ...
2
votes
1answer
44 views

Every 2-connected graph has a cycle of at least length 5

Is it true that every 2-connected simple graph of at least 10 vertices has at least one cycle of length 5 or more? I know that any two vertices lie on a common cycle and I am trying to use this by ...
0
votes
0answers
33 views

Graph theory and minor relation

I'm having some confusion with proposition $1.72$ of the Diestal book on Graph Theory which states that (ii) If $\Delta(X) \leq 3$, then every $MX$ contains $TX$ thus every minor with maximum degree ...
-1
votes
2answers
46 views

On 2- player game.

Consider the following 2-player game: you start with n tokens on a table, in a single pile. Players alternate turns. On a player's turn, they must choose one pile of their choice, and split it into ...
0
votes
1answer
34 views

Graph theory question, probably connected to Ramsey Theorem

Is the following statement true or false? For every $n > 0$, such $N$ exists, that no matter how we "color" all of the subsets of the set with $N$ elements(we only use two colors), No matter how ...
2
votes
2answers
23 views

possible polyhedra from euler's formula

I'm not very clear with the euler's formula, and I couldn't find it anywhere. I'm sorry if it is a double post. F + V - E = 2 Is the euler's formula. If the equation balances, is it polyhedra all ...
1
vote
0answers
29 views

Graph theory question about distances

Prove, that for every $n$, a $K(n)$ exists, that no matter how I place $K(n)$ points in the plane, there will always be at least $n$ different distances, that are specified with those points. My ...
2
votes
2answers
204 views

Size of matching

Prove that every graph G without isolated vertices has a matching of size at least n(G)/(1+∆(G)). (Hint: Apply induction on e(G)). I know that a perfect matching is the size of a minimum edge cover, ...
5
votes
0answers
43 views

A game may related to graph theory or topology

Last Sunday, I played a game with a group of people. The game is as follows: A group of people form a circle as shown below: Each person must remember how he/she is linked with his two neighbours. ...
0
votes
0answers
17 views

Graph Theory: Describing the maximum weight spanning tree

The question states, "Describe an algorithm for finding a spanning tree of maximum weight for a given weighted graph. Prove that your algorithm works." I researched and what I only know so far is ...
2
votes
2answers
28 views

Weakly connected graph test

What is the right algorithm for testing whether the graph is "weakly connected"? The theory says: Oriented graph $G=(V,E)$ is weakly connected graph if and only if for every two vertices $u,v \in ...
0
votes
1answer
56 views

Using Hall's Theorem to show something.

Suppose that there are five young women and five young men on an island. Each man is willing to marry some of the women on the island and each woman is willing to marry any man who is willing to marry ...
0
votes
1answer
31 views

Proof approach: A 7x7 matrix with 15 ones can allow at least three marriages

This is quite difficult to prove imho with regards to Hall's Marriage Algorithm I can visualize a number of scenarios that work (i.e. put ones from the first entry to the fifteenth, or across ...
0
votes
0answers
30 views

Prove that Hall's Condition is necessary for complete matching

Here's what I have so far: Hall's Algorithm states that given $n$ girls and $n$ boys a complete matching between the two groups is possible iff any of the three conditions are satisfied: There is ...
2
votes
2answers
360 views

Mantel's Theorem proof verification

I found the following proof for Mantel's proof. I cannot understand the equality that I have highlighted in the image was arrived at. I would appreciate some assistance thanks
1
vote
1answer
599 views

How can I tell how many non-isomorphic unrooted trees with 6 edges exists without drawing them all?

Typically my professor asks that we draw them all, but I would like to save some time to confirm how many I need.
1
vote
1answer
65 views

Prove that if G is a graph with no even cycles, then every cycle in G is an induced subgraph.

I tried using the contrapositive to prove the original statement: If no cycle in G is an induced subgraph, then G is a graph with no odd cycles. To prove this, I assumed that G did have an odd cycle ...
2
votes
1answer
108 views

Furthest distance vertices undirected tree

I know in my mind that it's very obvious, but I just can't seem to prove the following statement: Let $G$ be an undirected non-trivial tree with at least $3$ vertices. Let $u$ be an arbitrary vertex ...
0
votes
1answer
38 views

Maximum edge of a directed graph , if it contains weak components?

A digraph includes n nodes , and has two weak components , what is the maximum number of edges? ( there is no directed cycle)? Another question ,how does the answer change , if there is two strong ...
1
vote
1answer
13 views

How many edges could a cross-section of a polyhedron have?

We know that the cross-section of a cube could have 3, 4, 5, or 6 edges. But there could be no more. This can be explained in many ways: (1) The number of edges of a cross-section can't exceed the ...
1
vote
0answers
33 views

Max flow in flow network

My homework is to proof that if flow network has at least two max flows then it has infinity max flows. I know that I should not write it here since it is homework but I have been trying to solve ...
0
votes
4answers
37 views

Determine all graphs with matching number = 1

Determine all graphs G, without isolated vertices, such that the matching number=1. Could anyone help me this question? I am really confused about it. How to determine all possible graphs with this ...
1
vote
1answer
33 views

Planar Graph faces

let $G$ be a planar graph Prove that in any planar embedding of $G$, number of faces with odd degree is even. Also, prove that if G is not bipartite, then there are at least 2 faces with odd degree. ...
1
vote
2answers
119 views

Prove that if $G$ is an $r$-regular, $(r-2)$-edge-connected graph of even order containing at most $r-1$ distinct edge cuts then $G$ has a $1$-factor

Prove that if $G$ is an $r$-regular, $(r-2)$-edge-connected graph $(r>3)$ of even order containing at most $r-1$ distinct edge cuts of cardinality $r-2$ then $G$ has a $1$-factor Tutte's ...
0
votes
1answer
25 views

Graph skeleton for thorus $S_1$

Suppose the $g=1$ platonic graph with degree $d=3$ and the number of edges bounding each face is $n=6$ ($v=14$). Is this the skeleton of $S_1$ (the thorus with one hole)? We know that $K_7$ and the ...
0
votes
2answers
592 views

Prove that every connected graph of all whose vertices have even degree contain no bridges.

Prove that every connected graph of all whose vertices have even degree contain no bridges. I tried to prove this by induction. So let $G$ be a connected graph of order $n$. Since all vertices of $G$ ...
0
votes
1answer
21 views

Hamiltonian circuit in a Hamming graph

The problem is exactly what I have asked here: Showing that a particular graph is Hamiltonian Let $Q:=\{1,2,\ldots, q\}$. Let $G$ be a graph with the elements of $Q^n$ as vertices and an edge ...
1
vote
0answers
25 views

Chromatic number for sets of five or more elements

Definition. Given the set $D$ of positive integer numbers, we construct the distance graph for the integers, which vertices are $\Bbb{Z}$ and two numbers $x$ and $y$ are connected if the ...
1
vote
1answer
21 views

Deriving the probability of a node (vertex) on the end of a random chosen link (edge) having degree d.

From Jackson - Social and Economic Networks p. 87 (link: http://press.princeton.edu/chapters/s4_8767.pdf p.12 in pdf): (...) (T)he distribution of degrees of a node found by choosing a link ...
2
votes
1answer
61 views

How many subgraphs does a $4$-cycle have?

Question: How many subgraphs does a $4$-cycle have? I am trying to discover how many subgraphs a $4$-cycle has. I know that there will be $2^4=16$ subgraphs with no edges, but I am not sure how to ...
1
vote
1answer
301 views

adjacency matching in an undirected graph

I am having trouble understanding this concept, and have not found any good resources on google that explain it in a straightforward manner: An adjacency matching in an undirected graph G is a ...
4
votes
0answers
53 views

Number of subgraphs in the ladder graph

Assume you have the usual (in both directions infinite) ladder graph. I can try to provide a picture if needed. Further assume the vertices are labelled and I have one distinct vertex (call it the ...
1
vote
1answer
43 views

Collection of spanning trees for a simple connected graph

Consider a graph $G$ whose edges are labelled $\{1, 2, ..., k\}$. Then the set of spanning trees is a collection of subsets of $[k]$. a) Let $T$ = $\{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}\}$. Can $T$ be ...
2
votes
1answer
22 views

Let $r\geq 4$ and let $\delta (G)> (1-\frac{1}{r-1})|G|$. Show that every edge is contained in a $K_r$

Let $r\geq 4$ and let $\delta (G)> (1-\frac{1}{r-1})|G|$. Show that every edge is contained in a $K_r$ Hint: Pick the remaining vertices of the $K_r$ one by one. I'm at a loss as to what to do, ...
0
votes
0answers
39 views

Modifying Kruskal's algorithm for Maximum Spanning Tree

So in our class, we did a proof on Kruskal's algorithm for finding Minimum Spanning Tree. Now, based on that, I have to modify it to find me a Maximum Spanning Tree. I know the idea, taking ...
7
votes
2answers
464 views

Graph theory problem (edge-disjoint matchings)

Find the smallest number $x$ so that if an $n$-vertex simple graph has at least $x$ edges then it contains $k$ pairwise edge-disjoint perfect matchings* ($k$ is a positive integer, $n$ is an even ...
1
vote
2answers
38 views

Prove that every maximal planar graph of order 4 or more is 3-connected

I thought I might be able to use the fact that for a maximal planar graph the minimum degree of the graph is at least 3, but I couldn't figure anything out. Am I headed in the right direction? Where ...
1
vote
2answers
26 views

Proof related to maximum degree of node in a graph

So I'm given this problem - Prove that in every graph with 25 vertices, in which holds that in every 3-subset of vertices, at least two of them are connected, there exists a node of degree at least ...
0
votes
0answers
19 views

Best set of subgraphs of a weighted complete bipartite graph

Consider a weighted complete bipartite graph, i.e. consider the graph $G=(V,E)$, with $V=X \cup Y$, $X \cap Y = \emptyset$ and $E = X \times Y$, and a set of weights $W=\{w_i : i \in E\}$. Now we ...
1
vote
1answer
38 views

Number of edges in a digraph?

I know this might be similar to this question, but I would like to know what the maximum number of edges in a digraph would be if parallel edges (aka multi-edges) are not allowed. I know that the ...
1
vote
1answer
43 views

Tree-related problem, counting leafs

I am studying Graph Theory right now, and I have solved tons of problems so far. However, I got a tree-related problem, where it asks me to prove that a tree, in which maximum node degree is 6, the ...
1
vote
0answers
18 views

small expected contraction embedding into trees?

I learned FRT theorem for probabilistic metric embedding into trees: For any finite metric d, there exists a distribution over non contracting, small expected expansion tree metrics. The theorem can ...
3
votes
1answer
44 views

Proofs involving some general formulae for trees and binary trees.

So here I have 3 tree-related questions. 1) Let $n\geq2$ and let $d_1 ≤d_2 ≤···≤d_n$ be a sequence of integers. Show that there is a tree with degree sequence $d_1,d_2,...,d_n \Leftrightarrow \sum ...
0
votes
2answers
56 views

How many ways can the image be properly colored with at most q colors?

so the actual question is about the 8 regions of Iceland's political map, I just remapped it where each vertex is a different region and the edges represent which regions it boarders.The way I ...
1
vote
1answer
29 views

Establishing a bijection between binary vectors and threshold graphs.

So this is a theorem in my notes... A graph is threshold if and only if it can be created by means of two operations - starting with a single vertex 1) Add a dominating vertex (adjacent to all ...
0
votes
0answers
20 views

Probabilty of a path of length $D$ crossing partition exactly $k$ times

I am faced with a graph theory and probability question while doing my systems research. Suppose i have a Graph $G = (V,E)$ with $|V|$ vertices and $|E|$ edges. Now I partition the graph in $n$ parts ...