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

1
vote
1answer
29 views

Find the number of cycles and isolated vertices

I want the algorithm that allow me to find the number of cycles and isolated vertices from undirected graph. The isolated vertices means the vertices that are not connected to the root vertex, for ...
0
votes
0answers
10 views

Breadth first search tree

Suppose $G$ is a connected graph with breadth-first search tree $T_v$. I need to show that $$\sum_{v\in V} \sigma(T_v) \leq 2(n-1) \sigma(G),$$ where $\sigma(G) = \sum \{ d(u,v) \mid u,v \in V\}$. ...
0
votes
1answer
46 views

Motivation of the solution of a graph theory problem

The problem is: There is a math class with some students such that no matter what four students you choose there is always at least one that knows the other 3. (Note that knowing is symmetric, if A ...
0
votes
2answers
34 views

If $f$ is a cut edge in $G-e$, is $e$ a cut edge in $G-f$?

It seems not for any general $G$. But if $G$ is 2-connected does the hypothesis hold?
0
votes
1answer
17 views

Arguing that Graph, $G$, is 3 regular and pairwise edge-disjoint path can't share internal vertices

Let $G$ be a graph that is 3-regular. There are $n$ pairwise edge-disjoint $x,y$ paths. I want to show "since G is 3 regular, these paths cannot share internal vertices." I know the answer is supposed ...
1
vote
1answer
40 views

Hungarian Algorithm on Symmetric Matrix

I have a complete and weighted graph with an even number of vertices. I would like to separate all the vertices into pairs such that the sum of all the edge weights for each edge connecting the ...
1
vote
1answer
19 views

Explanation of proof: if a graph $G$ has no isolated vertices and no even cycle, then every block of G is an edge of cycle

If a graph $G$ has no isolated vertices and no even cycle, then every block of G is an edge of cycle A block with 2 vertices is an edge. (Got it) A block $H$ with more than 2 vertices is ...
0
votes
1answer
27 views

Applying Menger's theorem to a 2-connected graph to show there exist $k$ pairwise disjoint S,T paths

Let G be a 2-connected graph. S,T are disjoint subsets of V(G) with size at least $k$. Show that there exists $k$ pairwise disjoint S,T-paths. My current solution: Add a vertex $x$ adjacent to each ...
1
vote
2answers
45 views

Graph theory. Cities connected to other cities by roads.

In a certain country, 40 roads lead out of each city. When all roads are open, it is possible to travel from any city to any other. Each road leads from one city to another; there are no dead end ...
3
votes
3answers
29 views

Graph theory question involving people seated at a round table

50 mathematicians attend a conference at which each knows 25 other attendees. Show that you can select 4 of them who can then be seated at a round table, such that each person at the table knows the ...
2
votes
1answer
25 views

cut-edges, cycles, and a 2 connected graph

Read this statement in a textbook: If G - e - f is disconnected, then f is a cut-edge in G-e, whence f belongs to no edges in G-e, and thus every cycle in G containing f must contain also e. How can ...
1
vote
1answer
21 views

Menger's theorem and how many pairwise-edge disjoint paths?

In a proof, I came across this statement: ...
2
votes
1answer
36 views

On the number of cycles and independent edges in $K_{8}$

I am trying to find the number of cycles and $K_{2}$'s in $K_{8}$. That is, partition $8$ into all the ways such that the lowest part can be a $2$, so we have $8 = 8$, $6+2$, $5+3$, $2+3+3$, $4+4$, ...
0
votes
1answer
26 views

Largest and least amount of connected components of graph with conditions

A graph G without loops and parallel edges has the following properties:$$|V|=30$$$$|E|=30$$ It also has a cycle of length 10. What is the largest and the least amount of connected components in the ...
0
votes
1answer
17 views

suppose $L(G)$ is line graph of $G$ and k-regular,prove that $G$ is regular graph or bipartite of two kind of degree?

suppose $L(G)$ is line graph of $G$ and k-regular and is connected,prove that $G$ is regular graph or bipartite of two kind of degree? I made some classification: if $L(G)$ is k-regular and have ...
1
vote
1answer
27 views

Complexity of finding $\alpha(G) + \omega(G)$

The CLIQUE NUMBER problem is NP Complete (due to correspondence with $3$-SAT); so is the INDEPENDENCE NUMBER problem (since $\omega(\overline{G}) = \alpha(G)$, or from CHROMATIC NUMBER problem). Can ...
0
votes
2answers
23 views

Are there algorithms that traverse from two sides of a graph to find an s-t path.

Say I have a directed graph with a source and destination node s and t and I want to see if there's a path that exists between those two nodes. Intuitively I would think that the fastest way to do ...
0
votes
0answers
16 views

the matching problem of hungarian algorithm

a problem of matching for robot vertices to task vertices, there is a description: In our implementation we maintain the forest $F^{1}$ of all the alternating trees rooted in free task vertices. ...
0
votes
0answers
30 views

Creating a random network (graph) with a $\textbf{random}$ number of vertices and given degree distribution

I was trying to find an answer to my question on google scholar, however I didn't find anything that is close to what I am looking for. I would be very grateful for your help. There is a theory of ...
1
vote
0answers
22 views

Let $G$ be a graph of order $n$ with $\kappa (G) \geq 1$. Prove that $n> \kappa(G)[\operatorname{diam}(G)-1]+2$ [duplicate]

Let $G$ be a graph of order $n$ with $\kappa (G) \geq 1$. Prove that $n> \kappa(G)[\operatorname{diam}(G)-1]+2$ I know $\kappa(G) \leq n-1$. I do not know if do we have to prove it by ...
2
votes
1answer
22 views

Identifying the k points in 2D geographic space which are 'most distant' from each other

I have a set of DNA samples from Y plants in a given geographic area. I'm going to be doing DNA sequencing on individuals in this population (and a number of other, separate populations), however due ...
1
vote
1answer
49 views

Show that $\kappa(Q_n) =\lambda (Q_n)=n$ all positive integer $n$

Show that $\kappa(Q_n) =\lambda (Q_n)=n$ all positive integer $n$ I want to prove this by induction. so I start with $n=1$ Base: $n=1$ then $Q_1=K_2$, which have $\kappa(Q_1) =\lambda (Q_1)=1$. So ...
-1
votes
0answers
43 views

Count edges that can be removed

Given are N nodes and M edges, each edge connects two nodes. The edges are bidirectional , i.e., substance can flow in either direction through the edge. We start from node 1 and end up at node N. ...
0
votes
0answers
17 views

Connectivity of Subgraph

I want to prove the following theorem: A subgraph $H$ of $G$ is connected if and only if it contains an edge from every cut of $G$ that separates two of its vertices. My attempt: Let subgraph $H$ ...
0
votes
1answer
39 views

homeomorphic graphs

Are these graphs homeomorphic? a) and the Peterson graph? b) I think both are not homeomorphic.Is it correct?Is there a way I can show that they are not homemorphic Also two graphs being ...
1
vote
1answer
32 views

a graph $G$ of order $n \geq 2k$ is $k$ connected iff there exist $k$ pairwise disjoint paths connecting $V_1$ and $V_2$

Prove that a graph $G$ of order $n \geq 2k$ is $k$ connected if and only if for every 2 disjoint set $V_1$ and $V_2$ of $k$ distinct vertices each, there exist $k$ pairwise disjoint paths connecting ...
1
vote
2answers
49 views

Prove that $G$ is $k$ connected iff for each 2-vertex $T \subset S$, there is a cycle of $G$ that contain both vertices in $T$

Prove that $G$ of order $n \geq k+1 \geq 3$ is $k$ connected if and only if for each set $S$ of $k$ distinct vertices of $G$ and for each 2-vertex susbet $T$ of $S$, there is a cycle of $G$ that ...
1
vote
1answer
19 views

Disprove for every $k$ vertices of $G$ lies on a common cycle of $G$ for $k \geq 2$, $G$ is $k$ connected graph in general

Disprove for every $k$ vertices of $G$ lies on a common cycle of $G$ for $k \geq 2$, $G$ is $k$ connected graph I want to disporve this so I'm trying to show that $G$ is not a$$ connected graph. ...
0
votes
1answer
9 views

Support of vector $w$ in graph sparsity

I'm reading about graph sparsity and I have one problem in a paper I'm reading I don't understand, maybe someone can clarify: Graph Sparsity: In graph sparsity, we have a directed acyclic graph ...
0
votes
1answer
19 views

Planarity Criterion

I am looking for a proof of the theorem: If a planar graph, $G$, has $v$ vertices ($v \geq 3$) and no cycles of length 3 then, $e \leq 2v-4$. I remember doing this in a graph theory course and I ...
0
votes
1answer
35 views

Inductive proof. Every Graph has a path of length minimum degree

Hey could someone please check my proof that every graph has a path of length k where k is the minimum degree of the graph. I try to prove this by induction showing that every path with degree less ...
0
votes
1answer
30 views

Expression of the thresold with expected degree in a Random Geometric Graph

$n$ points ($P_i$) are distributed uniformly on the surface of an unit radius sphere. 2 points are interconnected if the distance between them is $\le r$ (thresold). We call the degree of point $i$ ...
0
votes
1answer
19 views

How to prove if $G$ is a $k-connected$ graph that adding $y$ and its $k$ neighbors to $G$ is also $k-connected$

Thm. If $G$ is a $k-connected$ graph, and $G'$ is obtained by adding a new vertex $y$, with at least $k$ neighbors in $G$, then $G'$ is also $k-connected$. Here's what I have so far: There are 4 ...
0
votes
2answers
12 views

Why does eigenvalue k of a regular graph of degree k have a multiplicity of one

Motivation There are lots of questions on here which link the "connectedness of a k regular graph and the multiplicity of its k eigenvalue", I understand their logic apart from the fact that they ...
2
votes
0answers
38 views

The width of a power set graph and its orientations

Let $G(\mathcal{P}(n),E)$ be the undirected graph for the power set of $[n]$ elements under the inclusion relation (i.e. a poset). The width of this poset - which is defined as the size of the maximum ...
1
vote
1answer
18 views

Clarification from a proof that a certain type of graph can be endowed with a group operation

I need some help sorting out a construction of a group out of the vertices of a digraph with a certain property. I'll just throw some definitions here first... Definitions. An alphabet ...
0
votes
1answer
21 views

Difference between cycle and simple cycle

In Graph Theory, what is the difference between a cycle and a simple cycle? My impression is that a simple cycle is the same as a cycle except that you cannot repeat vertices. Is this correct?
1
vote
2answers
52 views

How to calculate the number of automorphisms of a given graph?

How do determine the number of isomorphisms that a graph has to itself? For instance, suppose we have the following graph: How do I determine how many isomorphisms there are from G itself?
0
votes
1answer
23 views

True false question related to graph having a unique Minimum weight spanning tree

You have an undirected graph $G$ $G$ has a cycle in it That cycle has an edge $e$ e is a unique lightest weight edge in that cycle Is it true that $e$ is part of every Minimum weight spanning tree ...
4
votes
1answer
19 views

Bipartite Graph and Matches of Graph

We know that one match from $G=(V,E)$ be a subset of edges $M \subset_= E $ in such a way non two edges of M hasn't a common vertex. Matches M is Maximal if M not a proper subset of any other matches ...
3
votes
0answers
66 views

Research in graph theory

I am studying mathematics in a small university, this is my second year of my undergraduate degree. Recently I became interested in graph theory and would like to do some research, but there is no ...
5
votes
0answers
43 views

How can a finite graph be viewed as a discrete analogue of a Riemann surface?

In the paper "Riemann–Roch and Abel–Jacobi theory on a finite graph" by Baker and Norine, the first line of the abstract states: "It is well known that a finite graph can be viewed, in many respects, ...
1
vote
4answers
60 views

Actually playable games based on graphs?

In computer science lessons, we have recently got the task to program something using graphs. Due to my enthusiasm for computer games, i would really prefer to implement a concept for a game. The ...
1
vote
1answer
17 views

Prove that if $G$ is $k$-edge connected, then $G \bigvee K_1$ is $k+1$-edge connected.

Prove that if $G$ is $k$-edge connected, then $G \bigvee K_1$ is $k+1$-edge connected. Since $G$ is $k$-edge connected, $G$ has at least $k$ bridges. Let $H=G \bigvee K_1$, $X \subset E(H)$ , and ...
0
votes
1answer
26 views

is there a relation between regular graphs and power set graphs?

The title says it. Let $G(V,E)$ be a $k$-regular graph and $H(\hat{V},\hat{E})$ be the graph of the power set of $[k]$ elements (that is, $H$ resulted from the inclusion relation over the elements of ...
0
votes
1answer
15 views

¿What is a fundamental cycle? In the context of graphs

what is a fundamental cycle in graph theory? what does it imply? I already looked it up in wikipedia but it says very little
0
votes
1answer
23 views

Show that if $S$ is a vertex cut of cardinality $\kappa (G)$, then $G-S$ has at most $t$ components

Let $G$ be a non-complete graph of order $n$ and connectivity $k$ such that for every $v\in V(G)$, $deg(v) \geq \frac{n+kt-t}{t+1}$ for some $t \geq 2$. Show that if $S$ is a vertex cut of cardinality ...
0
votes
0answers
35 views

cardinality of maximum antichains in power set posets

Let $\mathcal{P}(S)$ be the power set of a non empty set $S$. Consider the poset $\succ$ for the inclusion relation over the elements of $\mathcal{P}(S)$ (which is equivalently represented by a single ...
1
vote
1answer
38 views

Planar graphs and connectivity

How many edges must a planar graph with $n$ nodes have that it is sure that it is a) connected b) biconnected c) triconnected In particular, are all planar graphs with $n$ nodes and $3n-6$ edges ...
1
vote
1answer
28 views

Prove that if $G$ is a $k-connected$ graph, then $G \bigvee K_1$ is $k+1$ connected graph

Prove that if $G$ is a $k-connected$ graph, then $G \bigvee K_1$ is $k+1$ connected graph Here is what I got so far Since $G$ is a $k-connected$ graph, there exists a vertex cut set $S \subset ...