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
1answer
12 views

Connectivity in Graph Theory if we add a new vertex in a k-connected graph

I am having trouble with my homework in graph theory. Someone can help me? Let v1,v2 ,...,vk be k distinct vertices of a K-connected graph G. Let H be the graph formed from G by adding a new vertex ...
1
vote
1answer
8 views

Question about trees, Let T be a tree with n vertices

Are my answers correct to these 3 questions? Let T be a tree with n vertices. 1) What is the average degree/valency of the vertices in T? Average Degree of of ...
0
votes
1answer
16 views

For a Cycle Graph is there only one Spanning tree?

For example a Cycle Graph C200 has only 1 spanning tree right? Because adding just one edge to a spanning tree will create a cycle?
0
votes
1answer
16 views

Proving a subgraph is regular

Given positive integer k, let H be the subgraph of Q_{2k+1} (a 2k+1 cube) induced by the vertices in which the number of ones and zeros differs by 1. Prove that H is regular and compute the order and ...
2
votes
0answers
26 views

A cycle of size at least $\frac{n}k$ in a graph with at least $3k$ vertices

My question is this: In a $G=(V,E)$ where $\alpha(G)\geq k$ (the maximum of the size of an independent subset of $G$) and $|V|=n\geq3k$, show that there is a cycle of size $\geq \frac{n}k$. Now, ...
1
vote
0answers
14 views

Algorithm to lay out orthogonal connector lines without overlap

I'm drawing a graph of nodes connected by orthogonal edges with corners. The nodes are laid out on a grid, and the edges (conceptually) follow the grid lines. The paths the edges take are laid out ...
0
votes
1answer
17 views

First order logic formula for complete graph with no self loops

I wanted to translate a party scenario where everyone shakes hands with everyone else into a first order logic statement. Since no one can shake hands with themselves, there can be no self loops. I ...
0
votes
1answer
12 views

Chromatic Number and Average degree

Is there any relation between average degree of a graph and chromatic number? Like if an average degree for a graph is 3.4. Can we say that the graph is not 2-colorable? for Number of edges = 17 and ...
0
votes
0answers
17 views

Edge choosability(edge list coloring) of bipartite graphs

It was proved by Galvin that the list chromatic index of bipartite multigraph $G$ equals to it's (ordinary) chromatic index: $$\chi_l'(G) = \chi'(G)$$ Let's use definition of choosability below: ...
1
vote
1answer
21 views

Possible eigenvalue of Laplacian

I came across an exercise of book Spectra of Graphs. Show that there does not exist graph whose adjacency matrix eigenvalue is -1/2. Any thougts?
2
votes
0answers
27 views

Algorithm to find the “optimal” path in a given graph

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...
1
vote
1answer
20 views

Star-Comb Lemma

I cannot understand that how can we apply Zorn's lemma here. What is the order set?
1
vote
0answers
11 views

Total number of possible graphs in a network with $m$ edges and $n$ vertices?

How do you calculate the total number of possible graphs in a network with $m$ undirected edges and $n$ vertices? No self-loops. For instance, if I have a network with $7$ vertices in it, I want to ...
0
votes
0answers
24 views

complete graphs and their properties.

Let $$G = K_{20}.$$ The number of edges in a complete graph is $$\frac{(n-1)n}2.$$ So for $n=20$ this is $(20)(19)/2 = 190.$ My question asks to calculate the minimum number of edges to be deleted ...
0
votes
1answer
22 views

How many spanning trees does the cycle graph C2014 have?

How many spanning trees does the cycle graph $C_{2014}$ have? How do I create a bipartite graph and use it to solve this problem?
0
votes
2answers
21 views

Minimum vertices set bipartite graph covering

I was wondering if anyone here could give me any pointers as to how to solve the following problem. Let B=(L,R,E) be an undirected bipartite graph, ∀u∈L, ∃ s= {ei(u,wi)} ∈E; i=1,2.....n connect u to ...
5
votes
0answers
46 views

Traveling salesman problem: can a terrible strategy beat a good one?

Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
0
votes
0answers
15 views

How many different graphs are there with a given degree-sequence?

Let G be a simple undirected graph. If it has at most $4$ edges, there is only one graph for any degree-sequence, but for $n = 5$, the situation changes. There are $34$ different (non-isomorphic) ...
6
votes
1answer
58 views

Traveling salesman problem: a worst case scenario

For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
1
vote
0answers
17 views

Meeting with R participants

A meeting has R participants. All participants arrive and leave at different times, but it is always true that within any 3 of them there is always at least 1, who has met the other 2. Prove that then ...
0
votes
0answers
18 views

Let G be a graph and M and N be maximum matchings in G. Characterize the subgraph G|_{M+N}

I have come across this problem from my graph theory study guide and I have no clue where to begin. This whole section is very confusing. Please help.
1
vote
1answer
32 views

Chromatic Triangles on a k17 graph

If the edges of the complete graph K17 (on 17 vertices with no three collinear) are each colored one of three colours can it be proven to have two or more monochromatic triangles?
6
votes
1answer
78 views

Graph with largest eigenvalue “almost” $\pi$

While doodling recently I found that the largest eigenvalue of the adjacency matrix of the following undirected graph (ignore directions on edges in picture) is "almost" $\pi$. According to octave ...
0
votes
1answer
30 views

Show that there is a path in $G$ contain three vertices whose degree are distinct

Show that if $G$ is a connected graph such that the degree of every vertex is one of 3 distinct number and each of these three number is degree of at least one vertex of $G$, then there is a path in ...
1
vote
1answer
34 views

“Job-scheduling” problem that minimizes the number of machines

In a graph, there are points that need to be visited. For each of these points, there is a certain time interval given by its start and ...
2
votes
0answers
36 views

Cubic 3-edge connected graph has edge cover that can omit 2/3 of all edges over 5 graphs (so 2/15 per graph) and be 2-edge connected

Let's assume that I have a cubic 3-edge connected simple graph $G$. After taking a perfect matching (and we can specify which one we want), I want to split the remaining edges in 5 sets $U_1, ..., ...
0
votes
0answers
10 views

Making a graph with information

I would like to ask what appropriate graph I should use and maybe an example to help me, I am struggling on what type of graph will be appropriate for this, and knowing could help me with the further ...
0
votes
1answer
12 views

Let $G$ be a disconnected graph of order $n \geq 6$ having three components. Prove that $\Delta(\overline G) \geq \frac{2n}{3}$

Let $G$ be a disconnected graph of order $n \geq 6$ having three components. Prove that $\Delta(\overline G) \geq \frac{2n}{3}$ This is what I got let $u \in V(G)$, since $G$ have three components, ...
0
votes
1answer
22 views

Prove that if $deg(u)+deg(v) \geq n-1$ for every two non adjacent vertices $u$ and $v$ of $G$ then $G$ is connected and $diam(G) \leq 2$

Let $G$ be a graph of order $n$. Prove that if $deg(u)+deg(v) \geq n-1$ for every two non adjacent vertices $u$ and $v$ of $G$ then $G$ is connected and $diam(G) \leq 2$ This is what I got so far ...
1
vote
1answer
35 views

Graph theory: tree vertices

How can I calculate the number of vertices of a tree knowing he has 33 vertices of degree 1, 25 vertices of degree 2, 15 vertices of degree 3 and all other vertices of grade 4?
0
votes
1answer
26 views

Minimal disjoint chains covering graph vertex set

I'm looking for references on the following problem: Given a graph $G=(V,E)$, what is the minimum number of simple, disjoint paths that span all the vertices in $V$? i.e., let $P$ be the answer to ...
1
vote
0answers
32 views

Example of infinite graph

First of all, I review some terms and notations. Let set of all ends of graph $G$ be $\Omega(G)$. For every end $\omega$ and every finite set $S\subseteq V(G)$, there is a unique component $C(S, ...
1
vote
4answers
43 views

Prove that if $\delta(G) \geq 2$ then $G$ contain a cycle

Prove that if $\delta(G) \geq 2$ then $G$ contain a cycle I tried to prove this using proof by contrapositive. I assume that $G$ has no cycle and show that $\delta(g) <2$. The smallest cycle we ...
1
vote
0answers
22 views

Ajacency matrix proof

Let $G_1, G_2,G_3$ be 3 graph of order $n$ and size $m$ having ajacency matrices $A_1,A_2,A_3$ respectively. a) Prove or disprove : $A_1=A_2$ implies $G_1 \cong G_2$ b) prove or disprove: $A_2 \neq ...
0
votes
2answers
38 views

Length of shortest path that visits every vertex

Suppose I have a connected graph with $n$ vertices and start in some arbitrary vertex $u$. I want to visit every vertex of the graph. I do not care about returning to where I started, and I can visit ...
0
votes
3answers
20 views

draw a undirected graph

Draw a undirected connected graph with 9 nodes, having degrees below. 2, 2, 2, 2, 2, 1, 1, 1, 1 I know that it will be having 7 edges, but how?? I am trying each time, I am stop after node 7, if I ...
3
votes
1answer
19 views

Proving every tree has at most one perfect matching

In trying to prove that every tree, T, has at most one perfect matching, I came across this idea: ...
0
votes
0answers
21 views

Distance between points in the plane [duplicate]

I have this problem and I honestly don't even have a clue of how to start, would someone help me please? Let $A$ = {$v_1$,$v_2$, . . . ,$v_n$} be a set of points in the plane such that the distance ...
1
vote
0answers
28 views

Which sequences $d_1,\ldots,d_n$ guarantee the planarity of a graph?

Which sequences $$d_1,\ldots,d_n$$ $$d_1\le \cdots\le d_n$$ have the property, that every graph with this degree sequence is planar ? It is clear that every sequence with $d_n\le 2$ works. As for ...
1
vote
0answers
10 views

Which degree sequences $d_1,…,d_n$ are planar-graphical?

Which degree sequences are planar-graphical, that means for which degree sequences $$d_1,...,d_n$$ $$d_1\le...\le d_n$$ exists a PLANAR graph that has this degree sequence ? I found some links in ...
0
votes
0answers
26 views

Chordless loops

How to find all chordless loops For example, given the graph the algorithm should return 1-2-3 and 0-1-3-4, but never 0-1-2-3-4.
2
votes
1answer
21 views

find all continuous path segments in an undirected graph

I have an undirected graph, like the following: . C . / \ . B F . / / \ . A D E The edges are: ...
0
votes
2answers
21 views

Terminology - variant of a hypergraph

In a hypergraph, we have vertices $V$ and hyperedges $H$, where each hyperedge is a subset of $V$. Suppose that we would like the hyperedges to be (ordered) tuples, rather than subsets. Does this ...
1
vote
0answers
21 views

How to draw Congressional districts to mirror the Popular Vote

Let me preface this by saying that I'm not sure whether this is fundamentally a mathematical question or not, but I think it is. In the United States, the House of Representatives is elected roughly ...
1
vote
0answers
22 views

What is the smallest $5$-vertex-connected ($5$-edge-connected) planar graph?

A planar graph cannot be $6$-connected because the number of edges of a planar graph with $n$ vertices is at most $3n-6$, while a $6$-connected graph with $n$ vertices must have at least $3n$ edges. ...
2
votes
1answer
42 views

Algebraic Combinatorics about a Finite Graph

Here is a problem listed on a book 'Algebraic Combinatorics' by Richard P.Stanley. Let $G$ be a finite graph with at least two vertices. Suppose that for some $l \ge 1$, the number of walks of ...
-2
votes
0answers
23 views

Determine the maximum of the minimum or given diameter. [closed]

Given $d\geq1$, determine $$\max_{\textrm{diam }G = d} \min\{\textrm{diam }T:T\textrm{ is a spanning tree of }G\}.$$
0
votes
1answer
34 views

Spanning tree with unique paths.

Let $G$ be a connected graph and let $r∈V(G)$. Prove that $G$ has a spanning tree $T$ such that for every edge of $G$ with ends $u$ and $v$, either $u$ belongs to the unique path in $T$ with ends $v$ ...
0
votes
0answers
11 views

How to draw dual of a directed graph? [duplicate]

How to assign directions in the dual drawn? I can draw a dual for a undirected graph,but in case of directed graph I'm confused about assigning directions to the edges in dual of directed graph.
1
vote
1answer
43 views

Graph triangle-free and maximun degree

Let G=(V,E) be a graph trangle free. a)Prove that $\Delta(G) \ge \frac{|V|}2$ b)Prove that there exists such a graph for |V|= 1,2 How would I prove this? particularly the part a) thanks