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

9
votes
3answers
565 views

What are some measures of connectedness in graphs?

I am not a mathematician (I am an engineer who is working on improving his mathematics), so I apologize in advance if my question is trivial. Consider a graph of $N$ nodes, with some defined ...
0
votes
1answer
153 views

Property of non-regular polyhedral graph the bound for number of faces

With just considering the number of edges that meet at a vertex, prove that f >= 2 + 1/3(e) So what I have is that a polyhedron is 3D so at least 3 edges will meet at each vertex, that's equivalent ...
0
votes
1answer
58 views

Projection of non-regular polyhedron onto graph?

Regular polyhedrons are planar graphs but are non-regular polyhedrons also planar such that Euler's formula V - E + F = 2 applies?
3
votes
3answers
1k views

prove $n$-cube is bipartite

prove $n$-cube is a bipartite graph for all $n\ge1$ This is a problem in my textbook and I cannot figure it out at all and have a test on graph theory tomorrow any help would be appreciated since I ...
1
vote
1answer
146 views

Find an expression for the number of edges of $L(G)$ in terms of the degrees of the vertices of $G$.

I have a hard time trying to understand this prove. Find an expression for the number of edges of $L(G)$ in terms of the degrees of the vertices of $G$. Let $\{v_1, v_2, . . . , v_n\}$ be the ...
0
votes
1answer
58 views

How can we create a graph $G'$ by subdividing the edge $e$ with a new degree two vertex $z$?

Let $G=(V,E)$ be a bipartite graph and e=uv an edge where $\text{deg}(u)<\Delta$. How can we create a graph G' by subdividing the edge e with a new degree two vertex z. i.e: we delete $e$ and ...
2
votes
0answers
113 views

graph theory homework

I have some problems with figuring out these questions about simple graphs. I'm not sure if I'm doing this right. 1.How many different graphs $G=(V,E)$ exist with $V=\{1,2,...,n\}$. There are ...
1
vote
1answer
588 views

Definition of induced cycle

According to Diestel (page 4): "If $G' \subseteq G$ and $G'$ contains all the edges $xy \in E$ with $x, y \in V'$, then $G'$ is an induced subgraph of $G$" According to Wikipedia "induced cycle is a ...
2
votes
1answer
787 views

The time complexity of finding a neighborhood graph provided an unordered adjacency matrix

Imagine I have an unordered adjacency matrix for some graph $G$ with a set of vertices $V$ and a set of edges $E$. I would like to find a subset of edges that determines a $k$-hop neighborhood graph ...
4
votes
1answer
76 views

Spanning tree with disconnecting set

How do i approach this problem? Assume $G$ is a connected graph and $e_1$ and $e_2$ are its edges such that every spanning tree of $G$ contains at least one of them. Prove that ...
1
vote
1answer
307 views

Ramsey-type result for tournaments

I'm working on the following questions but with no luck so I was hoping maybe someone can come up with help. Let $T$ be a tournament on $n$ vertices, say $\left\{v_{1},\ldots,v_{n}\right\}$, and let ...
1
vote
1answer
191 views

Bipartite graphs/ cartesian product

Prove that G and H are bipartite if any only if G x H is bipartite. (G x H denotes cartesian product) I saw someone else asked the same question, but the reply is only a hint on how to solve it. I am ...
0
votes
2answers
266 views

Graph Theory Question (Bipartite graph/Cartesian)

Prove that G and H are bipartite if any only if G x H is bipartite. Can anyone give me an idea of how to start this proof?
0
votes
2answers
112 views
1
vote
0answers
140 views

Topological sort of a subgraph of a multigraph

Is there a good algorithm for doing a topological sort of a subgraph of a multigraph? More specifically, given a multigraph G and a node n in the graph. Consider the subgraph G' all the nodes ...
0
votes
1answer
134 views

Bipartite Graph: Show that if $\deg(V_0)=3$, then we may $\Delta +1$ edge colour such a graph $G$.

Suppose that every odd cycle in a graph $G$ contains some specific vertex $V_0$ a) Give an example that shows that $\chi^E(G)$ may be larger than $\Delta$ b) Show that if $\deg(V_0)=3$, then we ...
2
votes
2answers
302 views

Fuzzy Venn diagram regions labeled in ternary

I have a couple of questions about the Venn diagrams object : Words from the binary alphabet with n letters label each region of an order-n Venn diagram. Is there any more profound connection ...
5
votes
1answer
373 views

The number of paths on a graph of a fixed length w/o repeatings

Sorry for bad English. Consider a graph $G$ with the adjacency matrix $A$. I know that the number of paths of the length $n$ is the sum of elements $A^n$. But what if we can't walk through a vertex ...
0
votes
1answer
43 views

Graph regular of degree 0, does Line graph exist?

If a graph is regular of degree 0, does a Line graph exist for it?
0
votes
1answer
181 views

Prove that the group of automorphisms of a labelled Cayley graph of a group G is the group G itself (Just stumped on one direction)

I feel like for this question it is just a matter of showing the mapping in both directions, from the group to the graph and the graph to the group. So for the mapping from the group to the graph, I ...
1
vote
0answers
22 views

What can we say about the liner graph of lexicographic product?

Let $G$ and $H$ be two graphs on vertex sets $V(G)$ and $ V(H)$, respectively. Then their lexicographic product $ G\circ H$ is a graph denoted by $ V(G\circ H)=V(G) \times V(H) $, and there is an edge ...
1
vote
0answers
100 views

When the lexicographic product of two graphs is edge transitive?

A graph $G$ is said to be edge transitive provided that, for any two edges $f$ and $g$ in $G$ , there is an automorphism of $G$ sending $f$ to $g$. Let $G$ and $H$ be two graphs on vertex sets $V(G)$ ...
4
votes
0answers
446 views

What is a bridgeless undirected planar 3-regular bipartite graph?

Draks asked a question about a sentence in Wikipedia stating that such-and-such (NP-hardness of Hamiltonian path detection) is true for "bridgeless undirected planar 3-regular bipartite graphs". What ...
10
votes
4answers
357 views

A problem about symmetric relations on finite sets.

We have these assumptions: $X$ is a finite set. $\sim$ is an irreflexive symmetric relation on $X$. for any subset $Y\subseteq X$ we define $$\mathcal{Cl}(Y)=\{A\subseteq Y\mid(\forall a,b\in ...
1
vote
1answer
120 views

NP-completeness for bridgeless undirected planar 3-regular bipartite graphs with face bounds

Wikipedia says that the ... Hamiltonian cycle problems ... remain NP-complete even ... for bridgeless undirected planar 3-regular bipartite graphs ... Fine. Are they still NP-complete when the ...
0
votes
1answer
146 views

Show that semi-symmetric graphs are bipartite

Any of the resources I've searched up have claimed that this is a trivial proof, but I just can't seem to see it. I've also seen the claim on wiki that all edge transitive graphs are bipartite, I'm ...
1
vote
0answers
32 views

Models for multiple graphs

I am trying to understand how to model multiple graphs. To make that concrete, I have two distinct graphs $\{V_1, E_1\}$ and $\{V_2, E_2\}$ where $V_i$ and $E_i$ are the node sets and the edge lists ...
3
votes
1answer
114 views

Robertson-Seymour fails for topological minor ordering? (I.e., subgraphs and subdivision)

The Robertson-Seymour theorem says that the set of isomorphism classes of finite graphs, with the minor ordering ($G \le H$ if $G$ is a minor of $H$) is a well partial ordering (it is well-founded and ...
2
votes
3answers
494 views

Graphs: trees, induction proof

I was wondering if you could help me prove the following. $G$ is a tree $\iff$ deleting any edge will disconnect it. And a similar one: $G$ is a tree $\iff$ adding any edge will create a cycle. I ...
0
votes
1answer
71 views

Does hamiltonian cycle have connections to four color problem other than history and Tait's conjecture?

According to Wikipedia and other sources, Tait's conjecture would have had significant effect on solving the FCP had it been true. Are there other mathematical connections between FCP and ...
0
votes
2answers
394 views

Confusion related to a graph problem

I have this question related to this graph problem Suppose that an n-node undirected graph G = (V , E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. ...
1
vote
2answers
471 views

Graphs such that $|G| \ge 2$ has at least two vertices which are not its cut-vertices

Show that every graph $G$, such that $|G| \ge 2$ has at least two vertices which are not its cut-vertices.
3
votes
1answer
866 views

Proof regarding Connected Graphs with even number of vertices.

I'm unsure as to how to go about continuing this proof. I have to prove that for an undirected graph $G = (V,E)$ where $n = |V|$ and $n$ is even, that the graph is connected for all $n \ge 2$, if ...
2
votes
1answer
52 views

Number of upper sets of size $n$ in a finite tree

Consider a finite tree $T = (V, <)$, where $y < x$ means that $y$ is the parent of $x$. We assume that $T$ has a unique root $r$ that has no parent. An upper set of $T$ is a subset $S$ of $V$ ...
0
votes
1answer
200 views

Chromatic Numbers for Graphs

Find the chromatic numbers of the following graphs: a graph $G_1$ obtained from $K_n$ by removing one edge a graph $G_2$ obtained from $K_n$ by removing two edges with a common vertex a graph ...
5
votes
1answer
120 views

Action of a subgroup of finite index on a tree induced by an action of a group on a tree

Let $G$ be a group wich acts on a tree $\Gamma$. Then $U$ acts on $\Gamma$ for every $U\leq G$. Question: Why does the following hold? If $|G:U|<\infty$. Then the minimal $U$-invariant subtree ...
2
votes
3answers
146 views

Counting graphs with even degrees

How many non-isomorphic distinct labeled 5-vertex graphs with even degrees are there? The answer is $2^6$, but I don't seem to be able to solve the problem. P.S. It's not a homework. I'm just ...
0
votes
1answer
48 views

What's the name for this sort of join?

I'm trying to describe a sort of join between two graphs $G$ and $H$ where you delete one edge from each graph (let's call the vertices adjacent to the deleted edges $g_1$, $g_2$, $h_1$ and $h_2$) , ...
3
votes
2answers
115 views

Lower bound on chromatic number of a family of graphs

Let $G_n$ be a graph whose vertices are the 2 element tuples of {$1,2,3...n$}. Two vertices ($i,j$) and ($k,ℓ$) are adjacent if and only if $i<j, k<ℓ$ and $j=k$ I am trying to show that the ...
1
vote
1answer
433 views

Number of connected / disconnected / total graphs with V vertices of degree d or d - 1

I've been at this for a couple of days now and I guess I just can't find a decent bijection to combinatorics for this. In the end what I really need is the probability of the graph to be connected / ...
5
votes
3answers
321 views

Are these two 10-vertex graphs isomorphic?

Explain if these two graphs are isomorphic. If so, give the 1-1 correspondence of nodes. I've checked that the two graphs have the same degrees, edges, and vertices, and check that they both aren't ...
0
votes
1answer
30 views

Total Permutation of tree if we combine n tree

I have n tree (acyclic graphs). If I join these n tree what will be total count of the tree? What I tried? I think if tree have ni vertex. Total tree will be: $n_1^{(n_1-2)}*n_2^{(n_2-2)}\cdots$ ...
1
vote
2answers
178 views

Graph theory: cycles

Prove that if two distinct cycles of a graph $G$ each contain an edge $e$, then $G$ has a cycle that does not contain $e$. My approach is since they both have edge e then if we remove edge $e$ from ...
1
vote
2answers
105 views

Total Permutation of graph with $n$ vertex?

Given there are $n$ vertex. How to calculate total number of distinct graph having all $n$ vertex. Is there any formula for that? Sorry one correction here: There is one more rule that there should ...
0
votes
1answer
223 views

Dirac's theorem question

Give an example to show that the condition $\deg(v) \geq n/2$ in the statement of Dirac's theorem cannot be replaced by $\deg(v) \geq (n-1)/2$ The textbook gives the solution: The complete bipartite ...
0
votes
2answers
2k views

Prove Petersen graph is not Hamiltonian using deduction and no fancy theorems

Prove Petersen graph is not Hamiltonian using basic terminology and deductions. I'm looking for an explanation without k-colouring or anything fancy like that since I haven't covered that in class. ...
3
votes
1answer
364 views

Graph theory dinner party problem

In a party of 6 people is it true that there exists four people either all do or all do not knowing each Other? I know it's false, and have the solution but not quite sure where to begin with the ...
2
votes
1answer
43 views

Euler graph - a question about the proof

I have a question about the proof of this theorem. A graph is Eulerian $\iff$ it is connected and all its vertices have even degrees. My question concerns "$\Leftarrow$" Let $T=(v_0, e_1, v_1, ..., ...
0
votes
1answer
226 views

Graph theory mutual acquaintance and mutual strangers problem

Show that there is a gathering of five people in which there are no three people who all know each other, and no three people none of whom knows either of the other two. There is a solution in the ...
10
votes
1answer
2k views

Proof : cannot draw this figure without lifting the pen

This question maybe ridiculous but I always found it interesting... Here it is : (I cannot put image so I put you the link of the pictures) When I was in school I used to draw houses when I was bored ...